Perhatikan graf acak dengan himpunan simpul \(\{1,2,\dots,n\}\text{.}\) Jika setiap sisi mempunyai probabilitas \(p=1/2\text{,}\) misalkan \(X\) menyatakan banyaknya klik berukuran \(t=2\log n\) dan \(Y\) menyatakan banyaknya himpunan bebas berukuran \(t=2\log n\text{.}\)
Tunjukkan bahwa \(E(X+Y)\lt 1\) apabila \(n\) cukup besar.
Gunakan hasil bagian a untuk menunjukkan bahwa \(\omega(G)\) kurang dari \(2\log n\text{,}\) sedangkan bilangan kromatik \(G\) sedikitnya \(n/(2\log n)\) (kedua pernyataan berlaku dengan probabilitas tinggi). Akibatnya, pertidaksamaan dasar \(\chi(G)\ge\omega(G)\) jauh dari tajam untuk graf acak.
Kita membentuk turnamen acak sebagai berikut. Mulailah dengan graf lengkap yang mempunyai himpunan simpul \(\{1,2,\dots,n\}\text{.}\) Untuk setiap pasangan berbeda \(i\text{,}\)\(j\) dengan \(1\le i\lt j\le n\text{,}\) lempar sebuah koin seimbang. Jika hasilnya sisi angka, arahkan sisi dari \(i\) ke \(j\text{,}\) yang kita nyatakan dengan \((i,j)\text{.}\) Jika hasilnya sisi gambar, arahkan sisi dari \(j\) ke \(i\text{,}\) yang dinyatakan dengan \((j,i)\text{.}\) Tunjukkan bahwa apabila \(n\) besar, pernyataan berikut berlaku dengan probabilitas tinggi: Untuk setiap himpunan \(S\) berukuran \(\log n/10\text{,}\) terdapat simpul \(x\) sedemikian sehingga \((x,y)\) merupakan sisi berarah dalam \(T\) untuk setiap \(y\in S\text{.}\)
Misalkan \(T\) merupakan turnamen acak pada \(n\) simpul. Tunjukkan bahwa pernyataan berikut berlaku dengan probabilitas tinggi: Untuk setiap pasangan simpul berbeda \(x\text{,}\)\(y\text{,}\) berlaku salah satu dari (1) \((x,y)\) merupakan sisi berarah dalam \(T\text{,}\) atau (2) terdapat simpul \(z\) sedemikian sehingga \((x,z)\) dan \((z,y)\) keduanya merupakan sisi berarah dalam \(T\text{.}\)
Banyak pernyataan tentang graf acak memperlihatkan perilaku ambang. Tunjukkan bahwa graf acak dengan probabilitas sisi \(p=10\log n/n\) hampir pasti tidak mempunyai simpul terisolasi, sedangkan graf acak dengan probabilitas sisi \(p=\log n/(10 n)\) hampir pasti mempunyai sedikitnya satu simpul terisolasi.
