Teorema Ramsey dan Bilangan Ramsey

Teorema Ramsey menjamin bahwa setiap graf lengkap dua warna yang cukup besar mengandung klik monokromatik, dan bilangan Ramsey mengukur seberapa besar yang cukup.

Definition

Bilangan Ramsey R(s,t) adalah bilangan bulat n terkecil sedemikian rupa sehingga setiap pewarnaan merah-biru pada sisi-sisi graf lengkap dengan n titik mengandung klik merah dengan s titik atau klik biru dengan t titik.

Scope

Topik ini mencakup bentuk graf dari teorema Ramsey, definisi bilangan Ramsey R(s,t), kasus-kasus kecil klasik seperti R(3,3)=6, batas atas Erdos-Szekeres dan batas bawah probabilistik Erdos, serta perluasan ke bilangan Ramsey multichromatic dan hipergraf. Ini adalah inti kuantitatif dari teori Ramsey.

Core questions

• Seberapa besar graf lengkap harus ada untuk memaksa klik monokromatik dengan ukuran tertentu?
• Berapa nilai pasti dan batas yang diketahui untuk bilangan Ramsey?
• Bagaimana argumen probabilistik memberikan batas bawah pada bilangan Ramsey?
• Bagaimana teorema ini digeneralisasi ke beberapa warna dan ke hipergraf?

Key concepts

• Teorema Ramsey untuk graf
• Bilangan Ramsey R(s,t)
• Klik monokromatik
• Batas Erdos-Szekeres
• Batas bawah probabilistik
• Bilangan Ramsey multichromatic dan hipergraf

Key theories

Batas atas Erdos-Szekeres

Bilangan Ramsey adalah hingga dan dibatasi oleh R(s,t) yang paling banyak merupakan koefisien binomial dari s+t-2 pilih s-1, batas berbasis rekurensi yang membuktikan teorema Ramsey dengan estimasi eksplisit.

Batas bawah probabilistik Erdos

Dengan menghitung ekspektasi klik monokromatik dalam pewarnaan acak, Erdos menunjukkan pada tahun 1947 bahwa bilangan Ramsey diagonal R(s,s) tumbuh setidaknya secara eksponensial, sebuah aplikasi pendiri dari metode probabilistik.

Clinical relevance

Metode probabilistik yang diperkenalkan melalui batas bawah bilangan Ramsey menjadi alat sentral di seluruh kombinatorika dan ilmu komputer teoretis, dan jaminan tipe Ramsey mendasari batas bawah dalam komunikasi dan struktur data.

History

Erdos dan Szekeres menemukan kembali dan menguantifikasi teorema Ramsey pada tahun 1935 saat mempelajari poligon cembung; batas bawah pewarnaan acak Erdos tahun 1947 meluncurkan metode probabilistik.

Key figures

• Frank Ramsey
• Paul Erdos
• George Szekeres

Seminal works

• graham1990

Frequently asked questions

Mengapa R(3,3) sama dengan enam?

Di antara enam orang, tiga di antaranya adalah kenalan bersama atau tiga di antaranya adalah orang asing bersama, sedangkan lima orang dapat diatur untuk menghindari keduanya, sehingga enam adalah ambang batas yang tepat.

Apakah bilangan Ramsey yang tepat diketahui?

Hanya segelintir yang diketahui secara tepat; bahkan R(5,5) masih terbuka, dengan pengetahuan saat ini hanya mempersempitnya ke suatu rentang, karena ruang pencarian tumbuh terlalu cepat untuk diselesaikan dengan komputasi.