Ramsey Teoremi ve Ramsey Sayıları
Ramsey teoremi, yeterince büyük iki renkli herhangi bir tam çizgenin tek renkli bir klik içerdiğini garanti etmekte; Ramsey sayıları ise bu yeterli büyüklüğün ne kadar olduğunu nicel olarak belirlemektedir.
Tanım
Ramsey sayısı R(s,t), n köşeli tam çizgenin kenarlarının her kırmızı-mavi renklendirmesinin s köşeli kırmızı bir klik veya t köşeli mavi bir klik içermesini sağlayan en küçük n tam sayısıdır.
Kapsam
Bu konu, Ramsey teoreminin çizge formunu, Ramsey sayıları R(s,t)'nin tanımını, R(3,3)=6 gibi klasik küçük durumları, Erdos-Szekeres üst sınırını ve Erdos'un olasılıksal alt sınırını, ayrıca çok renkli ve hiperçizge Ramsey sayılarına genişletilmesini kapsamaktadır. Ramsey teorisinin nicel özünü oluşturmaktadır.
Temel sorular
- Belirli büyüklükte tek renkli bir kliği zorlamak için tam bir çizge ne kadar büyük olmalıdır?
- Ramsey sayıları için bilinen kesin değerler ve sınırlar nelerdir?
- Olasılıksal argümanlar Ramsey sayıları üzerinde alt sınırları nasıl sağlamaktadır?
- Teorem, birden fazla renge ve hiperçizgelere nasıl genelleşmektedir?
Anahtar kavramlar
- Çizgeler için Ramsey teoremi
- Ramsey sayısı R(s,t)
- Tek renkli klikler
- Erdos-Szekeres sınırı
- Olasılıksal alt sınırlar
- Çok renkli ve hiperçizge Ramsey sayıları
Temel kuramlar
- Erdos-Szekeres üst sınırı
- Ramsey sayıları sonludur ve R(s,t)'nin en fazla (s+t-2)'nin (s-1)'lisi binom katsayısı olmasıyla sınırlıdır; bu, Ramsey teoremini açık tahminlerle kanıtlayan, tekrarlamaya dayalı bir sınırdır.
- Erdos'un olasılıksal alt sınırı
- Rastgele bir renklendirmede beklenen tek renkli klikleri sayarak Erdos, 1947'de köşegen Ramsey sayısı R(s,s)'nin en az üstel olarak büyüdüğünü göstermiştir; bu, olasılıksal yöntemin kurucu bir uygulamasıdır.
Klinik önem
Ramsey sayısı alt sınırları aracılığıyla tanıtılan olasılıksal yöntem, kombinatorik ve teorik bilgisayar biliminde merkezi bir araç haline gelmiş; Ramsey tipi garantiler ise iletişim ve veri yapılarındaki alt sınırların temelini oluşturmaktadır.
Tarihçe
Erdos ve Szekeres, 1935 yılında dışbükey çokgenleri incelerken Ramsey teoremini yeniden keşfetmiş ve nicel olarak ifade etmişlerdir; Erdos'un 1947'deki rastgele renklendirme alt sınırı ise olasılıksal yöntemi başlatmıştır.
Öne çıkan isimler
- Frank Ramsey
- Paul Erdos
- George Szekeres
İlgili konular
Temel eserler
- graham1990
Sıkça sorulan sorular
- R(3,3) neden altıya eşittir?
- Herhangi altı kişi arasında, üçü birbirini tanımakta veya üçü birbirine yabancı olmaktadır; beş kişi ise her iki durumu da önleyecek şekilde düzenlenebilmektedir, bu nedenle altı, kesin eşiktir.
- Kesin Ramsey sayıları bilinmekte midir?
- Sadece birkaçı kesin olarak bilinmektedir; R(5,5) bile hala açıktır ve mevcut bilgi sadece onu bir aralığa daraltmaktadır, çünkü arama alanı hesaplama yoluyla çözülemeyecek kadar hızlı büyümektedir.