Lewati ke konten utama

Subbab 16.7 Lemma Lokal Lovász

Meskipun manusia tampaknya sangat kesulitan memberikan konstruksi eksplisit bagi graf berukuran eksponensial yang tidak mempunyai subgraf lengkap ataupun himpunan bebas berukuran \(n\text{,}\) graf semacam itu ada dalam jumlah melimpah. Ambil saja sebuah graf secara acak dan hampir pasti Anda akan memperolehnya. Sebagai aturan umum, teknik probabilistik sering memberikan metode untuk mencari sesuatu yang jelas-jelas ada, tetapi sulit ditemukan.
Demikian pula, dalam bukti probabilistik tentang keberadaan graf dengan girth besar dan bilangan kromatik besar (Teorema 11.7), kita sebenarnya menunjukkan bahwa hampir semua graf mempunyai bilangan kebebasan berukuran sedang dan relatif sedikit siklus pendek, asalkan probabilitas sisi dipilih secara tepat. Siklus-siklus pendek tersebut dapat dihilangkan tanpa mengubah ukuran graf secara berarti.
Sebaliknya, dalam keadaan tertentu teknik probabilistik dapat digunakan untuk mencari sesuatu yang amat langka. Selanjutnya kita menyajikan hasil yang elegan tetapi elementer, yang dikenal sebagai Lemma Lokal Lovász dan telah terbukti sangat kuat. Pembahasannya disederhanakan oleh notasi alami berikut. Jika \(E\) merupakan kejadian dalam suatu ruang probabilitas, kita menggunakan \(\overline{E}\) untuk menyatakan komplemen \(E\). Selain itu, jika \(\cgF=\{E_1,E_2,\dots,E_k\}\text{,}\) kita menggunakan
\begin{equation*} \prod_{E\in\cgF}E=\prod_{i=1}^k E_i=E_1E_2E_3\dots E_k \end{equation*}
untuk menyatakan kejadian \(E_1\cap E_2\cap\dots\cap E_k\text{,}\) i.e., penulisan berdampingan merupakan singkatan bagi irisan. Notasi-notasi ini dapat dicampur, sehingga \(E_1\overline{E_2}\overline{E_3}\) menyatakan \(E_1\cap \overline{E_2}\cap\overline{E_3}\text{.}\) Sekarang misalkan \(\cgF\) keluarga kejadian hingga, \(E\in\cgF\text{,}\) dan \(\cgN\) subkeluarga \(\cgF-\{E\}\text{.}\) Dalam pernyataan lemma di bawah, kita mengatakan bahwa \(E\) saling bebas dengan setiap kejadian yang tidak berada dalam \(\cgN\) apabila
\begin{equation*} P(E|\prod_{F\in\cgG}\overline{F})=P(E) \end{equation*}
dengan syarat \(\cgG\cap\cgN=\emptyset\text{.}\)
Pertama, kita menyatakan dan membuktikan lemma dalam bentuk asimetris. Setelah itu, kita akan memberikan versi lebih sederhana yang disebut bentuk simetris.

Bukti.
Kita menggunakan induksi terhadap \(\cgG\text{.}\) Jika \(|\cgG|=1\) dan \(\cgG=\{E\}\text{,}\) kita hanya menyatakan bahwa \(P(\overline{E})\ge 1-x(E)\text{,}\) yang benar karena \(P(E)\le x(E)\text{.}\) Sekarang andaikan \(|\cgG|=k\ge2\) dan lemma berlaku setiap kali \(1\le |\cgG|\lt k\text{.}\) Misalkan \(\cgG =\{E_1,E_2,\dots,E_k\}\text{.}\) Maka
\begin{equation*} P(\prod_{i=1}^k \overline{E_i})=P(\overline{E_1}|\prod_{i=2}^k\overline{E_i}) P(\overline{E_2}|\prod_{i=3}^k\overline{E_i})P(\overline{E_3}|\prod_{i=4}^k\overline{E_i})\dots P(\overline{E_k}). \end{equation*}
Setiap faktor pada ruas kanan mempunyai bentuk berikut:
\begin{equation*} P(\overline{E}|\prod_{F\in\cgF_E}\overline{F}) \end{equation*}
dengan \(|\cgF_E|\lt k\text{.}\)
Jadi, kita selesai jika dapat menunjukkan bahwa
\begin{equation*} P(\overline{E}|\prod_{F\in\cgF_E}\overline{F})\ge 1- x(E) \end{equation*}
Hal ini ekuivalen dengan menunjukkan bahwa
\begin{equation*} P(E|\prod_{F\in\cgF_E}\overline{F})\le x(E) \end{equation*}
Mula-mula andaikan \(\cgF_E\cap\cgN(E)=\emptyset\text{.}\) Maka
\begin{equation*} P(E|\prod_{F\in\cgF_E}\overline{F})=P(E)\le x(E). \end{equation*}
Jadi, kita dapat mengandaikan \(\cgF_E\cap\cgN(E)\neq\emptyset\text{.}\) Misalkan \(\cgF_E=\{F_1,F_2,\dots,F_r,F_{r+1},F_{r+2},\dots, F_t\}\text{,}\) dengan \(F_i\in\cgN(E)\) jika dan hanya jika \(r+1\le i\le t\text{.}\) Maka
\begin{equation*} P(E|\prod_{F\in\cgF_E}\overline{F})= \frac{P(E\prod_{F\in\cgF_E\cap\cgN(E)}\overline{F}|\prod_{F\in\cgF_E-\cgN(E)}\overline{F})} {P(\prod_{F\in\cgF_E\cap \cgN(E)}\overline{F}|\prod_{F\in\cgF_E-\cgN(E)}\overline{F})} \end{equation*}
Tinjau terlebih dahulu pembilang dalam bentuk terakhir ini. Perhatikan bahwa
\begin{equation*} P(E\prod_{F\in\cgF_E\cap\cgN(E)}\overline{F}|\prod_{F\in\cgF_E-\cgN(E)}\overline{F})\le P(E|\prod_{F\in\cgF_E-\cgN(E)}\overline{F})=P(E)\le x(E)\prod_{F\in\cgN(E)}(1-x(F)). \end{equation*}
Berikutnya, tinjau penyebutnya. Berdasarkan hipotesis induksi, kita mempunyai
\begin{equation*} P(\prod_{F\in\cgF_E\cap\cgN(E)}\overline{F}|\prod_{F\in\cgF_E-\cgN(E)}\overline{F})\ge \prod_{F\in\cgF_E\cap\cgN(E)}(1-x(F)). \end{equation*}
Dengan menggabungkan kedua ketaksamaan terakhir, diperoleh
\begin{equation*} P(E|\prod_{F\in\cgF_E}\overline{F})\le x(E)\prod_{F\in\cgN(E)-\cgF_E}(1-x(F))\le x(E), \end{equation*}
dan bukti selesai.
Sekarang, berikut bentuk simetrisnya.

Bukti.
Tetapkan \(x(E)=1/(d+1)\) bagi setiap kejadian \(E\in\cgF\text{.}\) Maka
\begin{equation*} P(E)\le p< \frac{1}{e(d+1)}\le \frac{1}{d+1}(1-\frac{1}{d+1})^d \le x(E)\prod_{F\in\cgN(E)}(1-x(F)). \end{equation*}
Sejumlah penerapan bentuk simetris Lemma Lokal Lovász dinyatakan dengan syarat \(4pd\lt 1\text{.}\) Bukti bentuk alternatif ini hanyalah modifikasi sederhana dari argumen yang telah kita sajikan.
SblmKe AtasLnjt