Subbab 16.8 Menerapkan Lemma Lokal
Daftar penerapan Lemma Lokal terus bertambah, demikian pula minat terhadap penerapan lemma ini secara algoritmik, i.e., dalam konteks konstruktif. Namun, di sini kita menyajikan salah satu penerapan awalnya pada teori Ramsey—menaksir bilangan Ramsey \(R(3,n)\text{.}\) Ingat bahwa kita mempunyai ketaksamaan dasar \(R(3,n)\le \binom{n+1}{3}\) dari Teorema 11.2, sehingga wajar beralih ke metode probabilistik untuk mencari batas bawah yang baik. Namun, pemikiran singkat saja menunjukkan bahwa pendekatan ini menghadapi sejumlah tantangan.
Pertama, mari mencoba perhitungan langsung. Andaikan kita mencoba graf acak pada \(t\) simpul dengan probabilitas sisi \(p\text{.}\) Kita menginginkan tidak ada segitiga, sehingga diperlukan \(t^3p^3=1\text{,}\) i.e., \(p=1/t\text{.}\) Selanjutnya kita menginginkan tidak ada himpunan bebas berukuran \(n\text{,}\) yang memerlukan \(t^ne^{-pn^2}=1\text{,}\) i.e., \(n\ln t=pn^2\text{.}\) Jadi, kita bahkan tidak dapat membuat \(t\) lebih besar daripada \(n\text{.}\) Hal ini tidak membantu.
Kita dapat memperoleh hasil sedikit lebih baik dengan mengizinkan beberapa segitiga, lalu menghapus satu titik dari masing-masing segitiga, seperti yang dilakukan dalam bukti Teorema 11.7. Dengan cara ini, kita menetapkan \(t^3p^3=t\text{,}\) i.e., \(p=t^{-2/3}\text{.}\) Perhitungan tersebut sekarang menghasilkan batas bawah \(R(3,n)\ge n^{3/2}/\ln^{3/2} n\text{,}\) sehingga pangkat \(n\) pun masih berbeda dari batas atas.
Jadi, yang mana yang benar, atau apakah jawabannya berada di antaranya? Dalam makalah klasik tahun 1961, Erdős menggunakan penerapan metode probabilistik yang sangat cerdik untuk menunjukkan keberadaan graf yang menghasilkan batas bawah yang baik. Tekniknya memberikan batas bawah \(R(3,n)\ge n^2/\ln^2 n\text{,}\) sehingga pangkat dua pada \(n\) memang benar.
Di sini kita akan menggunakan Lemma Lokal Lovász untuk memperoleh batas bawah yang sama dengan cara yang jauh lebih langsung. Tinjau graf acak pada \(t\) simpul dengan probabilitas sisi \(p\text{.}\) Bagi setiap subhimpunan \(3\) elemen \(S\text{,}\) terdapat kejadian \(E_S\) yang terjadi ketika \(S\) membentuk segitiga. Bagi setiap himpunan \(n\) elemen \(T\text{,}\) terdapat kejadian \(E_T\) yang terjadi ketika \(T\) merupakan himpunan bebas. Dalam pembahasan berikut, kita sedikit menyalahgunakan notasi dengan menyebut kejadian \(E_S\) dan \(E_T\) masing-masing hanya sebagai \(S\) dan \(T\text{.}\) Perhatikan bahwa probabilitas \(S\) adalah \(p^3\) bagi setiap himpunan \(3\) elemen \(S\text{,}\) sedangkan probabilitas \(T\) adalah \(q=(1-p)^{C(n,2)}\sim e^{-pn^2/2}\) bagi setiap himpunan \(n\) elemen \(T\text{.}\)
Ketika menerapkan Lemma Lokal, kita menetapkan \(x=x(S)\) sebesar \(e^2p^3\) bagi setiap himpunan \(3\) elemen \(S\text{.}\) Kita juga menetapkan \(y=y(T)=q^{1/2}\sim e^{-pn^2/4}\text{.}\) Sebentar lagi akan jelas dari mana nilai-nilai tersebut berasal.
Selanjutnya, lingkungan suatu kejadian terdiri atas semua himpunan dalam keluarga yang mempunyai sedikitnya dua elemen bersama. Jadi, lingkungan himpunan \(3\) elemen \(S\) terdiri atas \(3(t-3)\) himpunan \(3\) elemen lainnya dan \(C(t-3,n-3)+3C(t-3,n-2)\) himpunan berukuran \(n\text{.}\) Demikian pula, lingkungan himpunan \(n\) elemen \(T\) terdiri atas \(C(n,3)+ (t-n)C(n,2)\) himpunan berukuran \(3\) dan \(\sum_{i=2}^{n-1}C(n,i) C(t-n,n-i)\) himpunan berukuran \(n\) lainnya. Jadi, ketaksamaan dasar yang perlu kita penuhi adalah:
\begin{align*}
p^3 \le \amp x(1-x)^{3(t-3)}(1-y)^{C(t-3,n-3)+3C(t-3,n-2)}\\
q \le \amp y(1-x)^{C(n,3)+(t-n)C(n,2)}(1-y)^{\sum_{i=2}^{n-1}C(n,i)C(t-n,n-i)}
\end{align*}
Selanjutnya, andaikan \(n^{3/2}\lt t\lt n^2\text{,}\) lalu gunakan aproksimasi biasa dengan mengabaikan suku berorde lebih kecil dan konstanta perkalian. Ketaksamaan-ketaksamaan tersebut dapat dipandang dalam bentuk sederhana berikut:
\begin{align*}
p^3 \le \amp x(1-x)^{t}(1-y)^{t^n}\\
q \le \amp y(1-x)^{tn^2}(1-y)^{t^n}
\end{align*}
Setelah dipikirkan sejenak, jelas bahwa kita ingin mempertahankan suku-suku yang memuat \((1-y)\) agar relatif besar, i.e., paling sedikit \(1/e\text{.}\) Hal ini pasti berlaku jika kita mempertahankan \(t^n\le 1/y\text{.}\) Syarat tersebut ekuivalen dengan \(n\ln t\le pn^2\text{,}\) atau \(\ln t\le pn\text{.}\)
Demikian pula, kita ingin mempertahankan suku \((1-x)^{t}\) agar relatif besar, sehingga kita menjaga \(t\le 1/x\text{,}\) i.e., \(t\le 1/p^3\text{.}\) Di sisi lain, kita hanya perlu mempertahankan suku \((1-x)^{tn^2}\sim e^{-xtn^2}\) paling sedikit sebesar \(y\text{.}\) Hal ini ekuivalen dengan mempertahankan \(xt\le p\text{,}\) dan karena \(x\sim p^3\text{,}\) syarat tersebut dapat ditulis ulang sebagai \(p^{-1}\ge t^{1/2}\text{.}\)
Sekarang kita mengetahui sasaran kita. Tetapkan saja \(\ln t=pn\) dan \(p^{-1}=t^{1/2}\text{.}\) Setelah substitusi, diperoleh \(t= n^2/\ln^2t\text{.}\) Karena \(\ln t=\Theta(\ln n)\) dalam tingkat ketelitian aproksimasi yang kita gunakan, diperoleh hasil yang diinginkan, yaitu \(t=\Theta(n^2/\ln^2n)\text{.}\)
