Lema 11.1.
Misalkan \(G\) merupakan sebarang graf dengan enam simpul atau lebih. Maka \(G\) memuat klik berukuran \(3\) atau himpunan bebas berukuran \(3\text{.}\)
Subbab 11.1 Sekilas Teori Ramsey
Bob suka menganggap dirinya liar dan gila, serta sama sekali tidak dapat diprediksi. Kebanyakan pria memang demikian. Namun, Alice mengatakan bahwa Bob tidak dapat mengubah sifat dasarnya yang luar biasa membosankan. Carlos berkomentar bahwa mungkin mereka tidak seharusnya terlalu keras kepada Bob, sebab dalam keadaan tertentu kita semua dapat dipaksa menjadi membosankan dan berulang-ulang.
Ingatlah bahwa apabila \(n\) merupakan bilangan bulat positif, kita menetapkan \([n]=\{1,2,\dots,n\}\text{.}\) Dalam bab ini, apabila \(X\) merupakan suatu himpunan dan \(k\) merupakan bilangan bulat tak negatif dengan \(k\le |X|\text{,}\) kita meminjam notasi sebaris untuk koefisien binomial dan menggunakan \(C(X,k)\) untuk menyatakan keluarga semua himpunan bagian \(k\)-elemen dari \(X\text{.}\) Jadi, \(|C([n],k)|=C(n,k)\) apabila \(0\le k\le n\text{.}\)
Ingatlah bahwa Prinsip Sarang Merpati menyatakan bahwa jika \(n+1\) merpati ditempatkan ke dalam \(n\) sangkar, harus ada suatu sangkar yang ditempati dua merpati atau lebih. Secara lebih formal, jika \(n\) dan \(k\) merupakan bilangan bulat positif, \(t>n(k-1)\text{,}\) dan \(f:[t]\longrightarrow[n]\) merupakan sebarang fungsi, maka terdapat suatu himpunan bagian \(k\)-elemen \(H\subseteq [t]\) dan suatu elemen \(j\in[n]\) sedemikian sehingga \(f(i)=j\) untuk setiap \(i\in H\text{.}\)
Sekarang kita mulai mempelajari perluasan yang elegan dari hasil dasar ini, yang terus memikat sekaligus menantang.
Kembali ke pembahasan pada awal bagian ini, kita dapat mengatakan bahwa subgraf terinduksi \(H\) dari graf \(G\) bersifat “membosankan” jika subgraf itu merupakan klik atau himpunan bebas. Dalam kedua kasus tersebut, setiap pasangan simpul dalam \(H\) berperilaku dengan cara membosankan yang sama persis. Jadi, apakah kebosanan tidak dapat dihindari? Jawabannya ya—setidaknya dalam arti relatif. Sebagai permulaan, mari kita tunjukkan bahwa setiap graf dengan enam simpul atau lebih mempunyai subgraf membosankan berukuran tiga.
Bukti.
Misalkan \(x\) merupakan sebarang simpul dalam \(G\text{.}\) Bagi simpul-simpul lainnya menjadi dua himpunan \(S_1\) dan \(S_2\text{,}\) dengan \(S_1\) terdiri atas tetangga-tetangga \(x\) dan \(S_2\) terdiri atas simpul-simpul yang bukan tetangga. Karena \(G\) mempunyai sedikitnya enam simpul, kita mengetahui bahwa \(|S_1|\ge 3\) atau \(|S_2|\ge 3\text{.}\) Pertama, misalkan \(|S_1|\ge 3\) dan pilih simpul-simpul berbeda \(y_1\text{,}\) \(y_2\text{,}\) dan \(y_3\) dari \(S_1\text{.}\) Jika \(y_iy_j\) merupakan sisi dalam \(G\) untuk suatu pasangan berbeda \(i, j\in\{1,2,3\}\text{,}\) maka \(\{x,y_i,y_j\}\) merupakan klik berukuran \(3\) dalam \(G\text{.}\) Di sisi lain, jika tidak ada sisi di antara simpul-simpul dalam \(\{y_1,y_2,y_3\}\text{,}\) kita memperoleh himpunan bebas berukuran \(3\text{.}\)
Argumen untuk kasus \(|S_2|\ge3\) bersifat dual.
Perhatikan bahwa batas enam dalam lemma sebelumnya bersifat tajam, sebab siklus pada lima simpul tidak memuat klik berukuran \(3\) maupun himpunan bebas berukuran \(3\text{.}\)
Berikut adalah pernyataan yang memperumum hasil tersebut.
Teorema 11.2. Teorema Ramsey untuk Graf.
Jika \(m\) dan \(n\) merupakan bilangan bulat positif, terdapat bilangan bulat positif terkecil \(R(m,n)\) sedemikian sehingga apabila \(G\) merupakan graf dan \(G\) mempunyai sedikitnya \(R(m,n)\) simpul, maka \(G\) memuat klik berukuran \(m\) atau \(G\) memuat himpunan bebas berukuran \(n\text{.}\)
Bukti.
Kita menunjukkan bahwa \(R(m,n)\) ada dan paling besar \(\binom{m+n-2}{m-1}\text{.}\) Pernyataan ini langsung diperoleh jika \(m\le 2\) atau \(n\le2\text{,}\) sehingga kita dapat mengasumsikan \(m,n\ge3\text{.}\) Selanjutnya, kita menggunakan induksi pada \(t=m+n\text{,}\) dengan kasus \(t\le 5\) sebagai kasus dasar.
Sekarang misalkan \(x\) merupakan sebarang simpul dalam \(G\text{.}\) Terdapat sedikitnya \(\binom{m+n-2}{m-1}-1\) simpul lain, yang kita partisi sebagai \(S_1\cup S_2\text{,}\) dengan \(S_1\) terdiri atas simpul-simpul yang bertetangga dengan \(x\) dalam \(G\) dan \(S_2\) terdiri atas simpul-simpul yang tidak bertetangga dengan \(x\text{.}\)
Ingatlah bahwa koefisien binomial memenuhi
\begin{align*}
\binom{m+n-2}{m-1} \amp=\binom{m+n-3}{m-2}+\binom{m+n-3}{m-1}\\
\amp = \binom{m+n-3}{m-2}+\binom{m+n-3}{n-2}\text{.}
\end{align*}
Dengan demikian, \(|S_1|\ge \binom{m+n-3}{m-2}\) atau \(|S_2|\ge\binom{m+n-3}{m-1}\text{.}\)
Jika kemungkinan pertama berlaku dan \(S_1\) tidak mempunyai himpunan bebas berukuran \(n\text{,}\) maka \(S_1\) memuat klik berukuran \(m-1\text{.}\) Dengan menambahkan \(x\) ke himpunan tersebut, kita memperoleh klik berukuran \(m\) dalam \(G\text{.}\)
Demikian pula, jika kemungkinan kedua berlaku dan \(S_2\) tidak memuat klik berukuran \(m\text{,}\) maka \(S_2\) memuat himpunan bebas berukuran \(n-1\text{;}\) dengan menambahkan \(x\) ke himpunan tersebut, kita memperoleh himpunan bebas berukuran \(n\) dalam \(G\text{.}\)
