Batas bawah pada ukuran interval maksimum yang diinduksi subgraf grafik

Misalkan adalah subgraph interval maksimum yang diinduksi dari grafik . Jika， Lalu berapakah jumlah terkecil ?G = ( V , E ) n = | V | V ( H $H$$G=(V,E)$$n=|V|$$V(H)$

Jumlahnya paling banyak： pertimbangkan seperangkat lubang terpisah.$3n/4$$4$

Bisakah ini lebih kecil?

Saya pikir jawabannya adalah $\Theta(\log n)$ dan buktinya sama dengan bukti klasik Ramsey-theorem. Di satu sisi, Anda selalu memiliki teks lengkap atau kosong dengan banyak simpul ini. Di sisi lain, grafik acak tidak akan memiliki diinduksi besar $C_4$ -gratis subgraph. Untuk yang terakhir ini, terikat jumlah subgraphs diinduksi pada $t$ simpul oleh $n^t$ dan untuk setiap terikat probabilitas menjadi $C_4$ -gratis oleh $c^{t^2}$ di mana $c<1$ adalah beberapa konstan. Ini bisa kita lakukan karena grafik lengkap pada $t$ simpul berisi $\Omega(t^2)$ memisahkan$K_4$ .

Secara lebih rinci, bagi sisi yang mungkin di antara simpul apa pun menjadi klik-klik terpisah dari empat simpul. Dalam klik empat simpul seperti itu, probabilitas bahwa ujung-ujungnya tidak akan membentuk adalah konstan . Oleh karena itu probabilitas bahwa tidak akan ada di salah satu klik adalah . Ini jelas merupakan batas atas untuk grafik acak menjadi -gratis.$t\choose 2$$t$$\Omega(t^2)$$C_4$$p<1$$C_4$$p^{\Omega(t^2)}$$C_4$

Kita dapat melakukan ; pertimbangkan grafik lengkap , selama ada dua pihak yang keduanya memiliki lebih dari satu node di dalam ada diinduksi , jadi tidak bisa inteval. Karena itu kita harus menghapus setidaknya node untuk menghancurkan semua diinduksi .$2\sqrt{n}-1$ C4($\sqrt{n}$$C_4$C$(\sqrt{n}-1)^2 = n - 2\sqrt{n} + 1$$C_4$