Teorema 11.7. Erdős.
Untuk setiap pasangan bilangan bulat \(g,t\) dengan \(g\ge3\text{,}\) terdapat graf \(G\) dengan \(\chi(G)>t\) dan girth \(G\) lebih besar daripada \(g\text{.}\)
Subbab 11.6 Metode Probabilistik
Pada awal bab ini, kita menyajikan bukti asli Erdős untuk batas bawah bilangan Ramsey \(R(n,n)\) dengan menggunakan pencacahan. Kemudian, kita merumuskan kembali bukti tersebut dalam kerangka probabilistik. Sejarah menunjukkan bahwa sudut pandang kedua inilah yang tepat. Untuk memperlihatkan kekuatan pendekatan ini, kita menyajikan sebuah teorema klasik lain dari Erdős yang menunjukkan adanya graf dengan girth besar dan bilangan kromatik besar.
Girth \(g\) dari suatu graf \(G\) adalah bilangan bulat terkecil sedemikian sehingga \(G\) memuat siklus pada \(g\) simpul. Girth sebuah hutan dianggap tak hingga, sedangkan girth suatu graf sama dengan tiga jika dan hanya jika graf tersebut mempunyai segitiga. Anda dapat memeriksa keluarga graf bebas segitiga dengan bilangan kromatik besar yang dibangun dalam Bab 5 dan melihat bahwa masing-masing mempunyai girth empat.
Bukti.
Sebelum membahas perincian argumen, mari kita berhenti sejenak untuk memahami gagasan umum di balik bukti tersebut. Kita memilih bilangan bulat \(n\) dan \(s\) dengan \(n>s\text{;}\) pada akhirnya akan jelas seberapa besar keduanya perlu dipilih dalam hubungannya dengan \(g\) dan \(t\text{.}\) Kemudian kita meninjau graf acak pada himpunan simpul \(\{1,2,\dots,n\}\text{.}\) Seperti sebelumnya, untuk setiap \(i\) dan \(j\) dengan \(1\le i\lt j\le n\text{,}\) probabilitas bahwa pasangan \(ij\) merupakan sisi ialah \(p\text{,}\) tetapi sekarang \(p\) bergantung pada \(n\text{.}\) Tentu saja, untuk pasangan-pasangan yang berbeda, kejadian bahwa pasangan tersebut merupakan sisi saling bebas.
Tujuan pertama kita ialah memilih nilai \(n\text{,}\) \(s\text{,}\) dan \(p\) sedemikian sehingga dengan probabilitas tinggi, suatu graf acak tidak mempunyai himpunan bebas berukuran \(s\text{.}\) Anda mungkin mengira bahwa tujuan kedua ialah memperoleh graf acak tanpa siklus pendek. Namun, tujuan itu terlalu membatasi. Sebagai gantinya, kita hanya berusaha memperoleh graf yang memiliki relatif sedikit siklus pendek. Tepatnya, kita menginginkan banyaknya siklus pendek kurang dari \(n/2\text{.}\) Kemudian kita menghapus satu simpul dari setiap siklus pendek, sehingga diperoleh graf dengan sedikitnya \(n/2\) simpul, tanpa siklus pendek, dan tanpa himpunan bebas berukuran \(s\text{.}\) Bilangan kromatik graf ini sedikitnya \(n/(2s)\text{,}\) sehingga kita menginginkan pertidaksamaan \(n>2st\text{.}\)
Sekarang perhatikan beberapa perinciannya. Misalkan \(X_1\) merupakan peubah acak yang menghitung banyaknya himpunan bebas \(s\)-elemen. Maka
\begin{equation*}
E(X_1)=\binom{n}{s}(1-p)^{C(s,2)}
\end{equation*}
Kita menginginkan \(E(X_1)\lt 1/4\text{.}\) Karena \(C(n,s)\le n^s=e^{s\ln n}\) dan \((1-p)^{C(s,2)}\le e^{-ps(s-1)/2}\text{,}\) untuk ukuran graf yang cukup besar kita dapat memilih \(s=3\ln n/p\text{.}\) Berdasarkan Ketaksamaan Markov, probabilitas bahwa \(X_1\) melebihi \(1/2\ge 2E(X_1)\) kurang dari \(1/2\text{.}\)
Sekarang misalkan \(X_2\) menghitung banyaknya siklus dalam \(G\) yang berukuran paling besar \(g\text{.}\) Maka
\begin{equation*}
E(X_2)\le \sum_{i=3}^g n(n-1)(n-2)\dots(n-i+1) p^i\le g(pn)^g.
\end{equation*}
Kita menginginkan \(E(X_2)\le n/4\text{,}\) dan perhitungan sederhana menunjukkan bahwa \(g(np)^g\le n/4\) apabila \(p=n^{1/g-1}/10\text{.}\) Sekali lagi berdasarkan Ketaksamaan Markov, probabilitas bahwa \(X_2\) melebihi \(n/2\ge 2E(X_2)\) kurang dari \(1/2\text{.}\)
Kita menyimpulkan bahwa terdapat graf \(G\) dengan \(X_1=0\) dan \(X_2\le n/2\text{.}\) Hapus satu simpul dari setiap siklus pendek dalam \(G\text{,}\) dan misalkan \(H\) merupakan graf yang tersisa. Jelas bahwa \(H\) mempunyai sedikitnya \(n/2\) simpul, tidak mempunyai siklus berukuran paling besar \(g\text{,}\) dan tidak mempunyai himpunan bebas berukuran \(s\text{.}\) Terakhir, pertidaksamaan \(n>2st\) mensyaratkan \(n^{1/g}/(60\ln n)>t\text{.}\)
Subbagian 11.6.1 Membangun Intuisi dengan Metode Probabilistik
Peneliti berpengalaman mampu menyederhanakan perhitungan dalam argumen semacam ini karena mereka mengetahui apa yang dapat diabaikan dengan aman dan apa yang tidak. Berikut tinjauan singkat atas langkah-langkah utamanya. Kita menginginkan \(E(X_1)\) kecil, sehingga kita menetapkan \(n^se^{-ps^2}=1\) dan memperoleh \(s=\ln n/p\text{.}\) Kita menginginkan banyak siklus pendek sekitar \(n\text{,}\) sehingga kita menetapkan \((np)^g=n\) dan memperoleh \(p=n^{1/g-1}\text{.}\) Terakhir, kita menginginkan \(n=st\text{,}\) yang mensyaratkan \(n^{1/g}=t\ln n\text{.}\) Selebihnya hanyalah memperhatikan perinciannya.
