Grafik Kepadatan Ramsey

Misalkan kita memiliki grafik dengan n simpul yang tidak mengandung klik log ukuran 3 ( n ) atau kumpulan log ukuran 3 yang independen ( n ) (misalnya G ( n , 0,5 ) memenuhi properti ini dengan probabilitas tinggi). Apakah benar bahwa jumlah tepi G setidaknya n 2 / 100 , yaitu, itu tidak terlalu jarang?$G$$n$$3 \log(n)$$3 \log(n)$$G(n,0.5)$$G$$n^2/100$

Secara umum, saya ingin tahu apakah grafik semacam itu memiliki beberapa sifat pseudo-acak.

Jawaban atas pertanyaan Anda adalah ya. Ini adalah hasil Erdős dan Szemerédi dari tahun 1972 . Kita tahu sedikit, tetapi tidak nol tentang sifat pseudo-acak grafik Ramsey. Sebagai contoh, kita tahu bahwa banyak jenis subgraph yang diinduksi muncul dalam grafik seperti itu. Lihat, misalnya, makalah karya Alon – Balogh – Kostochka – Samotij dan referensi di dalamnya.