Teorema 11.4.
Jika \(n\) merupakan bilangan bulat positif, maka
\begin{equation*}
R(n,n) \ge \frac{n}{e\sqrt2} 2^{\frac{1}{2}n}
\end{equation*}
Subbab 11.4 Menerapkan Probabilitas pada Teori Ramsey
Teorema berikut, yang berasal dari P. Erdős, benar-benar merupakan hasil klasik dan disajikan di sini dengan cara yang setia pada publikasi pertamanya. Seperti akan kita lihat nanti, teorema tersebut kemudian dirumuskan kembali—tetapi janganlah kita mendahului pembahasan.
Bukti.
Misalkan \(t\) merupakan bilangan bulat dengan \(t>n\) dan perhatikan himpunan \(\cgF\) yang terdiri atas semua graf berlabel dengan himpunan simpul \(\{1,2,\dots,t\}\text{.}\) Jelas terdapat \(2^{C(t,2)}\) graf dalam keluarga ini. Misalkan \(\cgF_1\) menyatakan subkeluarga yang terdiri atas graf-graf yang memuat klik berukuran \(n\text{.}\) Mudah dilihat bahwa
\begin{equation*}
|\cgF_1|\le \binom{t}{n}2^{n(t-n)}2^{C(t-n,2)}.
\end{equation*}
Demikian pula, misalkan \(\cgF_2\) menyatakan subkeluarga yang terdiri atas graf-graf yang memuat himpunan bebas berukuran \(n\text{.}\) Dengan demikian,
\begin{equation*}
|\cgF_2|\le \binom{t}{n}2^{n(t-n)}2^{C(t-n,2)}.
\end{equation*}
Kita ingin mengambil bilangan bulat \(t\) sebesar mungkin sambil tetap menjamin bahwa \(|\cgF_1|+|\cgF_2|\le |\cgF|\text{.}\) Hal ini menyiratkan bahwa terdapat graf \(G\) dalam \(\cgF\) yang tidak memuat klik berukuran \(n\) maupun himpunan bebas berukuran \(n\text{.}\) Jadi, perhatikan pertidaksamaan berikut:
\begin{equation}
2\binom{t}{n}2^{n(t-n)}2^{C(t-n,2)}\lt 2^{C(t,2)}.\tag{11.4.1}
\end{equation}
Sekarang kita bertanya: seberapa besar \(t\) dapat dipilih tanpa melanggar pertidaksamaan (11.4.1)? Untuk menjawabnya, kita menggunakan pertidaksamaan sederhana \(\binom{t}{n}\le t^n/n!\) dan aproksimasi Stirling untuk \(n!\text{.}\) Setelah melakukan manipulasi aljabar dan mengambil akar ke-\(n\) pada kedua ruas, kita melihat bahwa cukup dijamin
\begin{equation*}
t\le \frac{n}{e\sqrt{2}}2^{\frac{1}{2}n}
\end{equation*}
Sekarang mari kita tinjau kembali bukti Teorema 11.4. Kita meninjau ruang probabilitas \((S,P)\) yang hasil-hasilnya berupa graf dengan himpunan simpul \(\{1,2,\dots,t\}\text{.}\) Untuk setiap \(i\) dan \(j\) dengan \(1\le i \lt j\le t\text{,}\) sisi \(ij\) terdapat dalam graf dengan probabilitas \(1/2\text{.}\) Selain itu, kejadian-kejadian untuk pasangan yang berbeda saling bebas.
Misalkan \(X_1\) menyatakan peubah acak yang menghitung banyaknya himpunan bagian \(n\)-elemen dari \(\{1,2,\dots,t\}\) dengan semua \(\binom{n}{2}\) pasangannya merupakan sisi dalam graf. Demikian pula, \(X_2\) merupakan peubah acak yang menghitung banyaknya himpunan bebas berukuran \(n\) dari \(\{1,2,\dots,t\}\text{.}\) Kemudian tetapkan \(X=X_1+X_2\text{.}\)
Berdasarkan linearitas nilai harapan, \(E(X)=E(X_1)+E(X_2)\text{,}\) sedangkan
\begin{equation*}
E(X_1)=E(X_2) = \binom{t}{n} \frac{1}{2^{C(n,2)}}.
\end{equation*}
Jika \(E(X)\lt 1\text{,}\) harus ada graf dengan himpunan simpul \(\{1,2,\dots,t\}\) yang tidak memuat \(K_n\) maupun \(I_n\text{.}\) Pertanyaan tentang seberapa besar \(t\) dapat dipilih sambil mempertahankan \(E(X)\lt 1\) membawa kita tepat pada perhitungan yang sama seperti sebelumnya.
Setelah lebih dari lima puluh tahun dan upaya banyak peneliti yang sangat cemerlang, hanya sedikit perbaikan yang berhasil dicapai pada batas untuk \(R(n,n)\) dari Teorema 11.2 dan Teorema 11.4. Secara khusus, belum ada yang dapat menentukan apakah terdapat konstanta \(c\lt 2\) dan bilangan bulat \(n_0\) sedemikian sehingga \(R(n,n)\lt 2^{cn}\) apabila \(n>n_0\text{.}\) Demikian pula, belum ada yang dapat menjawab apakah terdapat konstanta \(d>1/2\) dan bilangan bulat \(n_1\) sedemikian sehingga \(R(n,n)>2^{dn}\) apabila \(n>n_1\text{.}\) Kami tentu akan memberi Anda nilai \(A\) untuk mata kuliah ini jika Anda berhasil menyelesaikan salah satunya.
Diskusi 11.5.
Carlos mengatakan bahwa ia telah mencoba membuktikan batas bawah yang baik untuk \(R(n,n)\) hanya dengan metode konstruktif, i.e., tanpa memperbolehkan teknik acak. Namun, ia mengalami kesulitan. Semua yang dicobanya tampaknya hanya menunjukkan bahwa \(R(n,n)\ge n^c\) dengan \(c\) suatu konstanta. Hasil itu tampak sangat lemah dibandingkan dengan batas eksponensial yang mudah diberikan oleh metode probabilistik. Biasanya Alice tidak terlalu bersimpati pada keluhan orang lain, apalagi keluhan Carlos yang tampaknya selalu berada di depan. Namun kali ini, Alice berkata kepada Carlos dengan suara yang dapat didengar semua orang, “Mungkin kamu tidak seharusnya terlalu keras kepada dirimu sendiri. Aku membaca artikel di web yang mengatakan bahwa belum ada seorang pun yang berhasil menunjukkan adanya konstanta \(c>1\) dan bilangan bulat \(n_0\) sedemikian sehingga \(R(n,n)>c^n\) apabila \(n>n_0\text{,}\) jika hanya metode konstruktif yang diperbolehkan. Dan mungkin, hanya mungkin, mengatakan bahwa kamu tidak mampu melakukan sesuatu yang tampaknya juga tidak mampu dilakukan banyak tokoh terkenal bukanlah hal yang terlalu buruk.” Bob melihat sisi baru Alice, dan hal itu pun tidak terlalu buruk.
