Ramsey Sayısı | Matematik Blogu
← Galois Teorisi Nedir?
1729 (Taksi Numarası) →
Köşe sayısı olan tam çizge , her kenarı kırmızı veya mavi olacak şekilde boyanıyor. Bu şekilde verilen bir çizge içinde bütün kenarları aynı renk olan köşeli tam bir alt çizge oluştuğunu hangi değerleri için garanti edebiliriz?
Örneğin ve aldığımızda sorumuzun cevabını olumsuz yapacak bir örnek bulabiliyoruz. Aşağıdaki durumda köşe sayısı olan tek renkli tam bir çizge, yani kırmızı veya mavi bir üçgen, oluşturmak mümkün değil.
sayısını sabit tutup, değerini bir arttırdığımızda cevabın olumlu olacağını görmek çok zor değil. Köşelere dersek, her hangi bir köşeye ya üç kırmızı ya da üç mavi kenar (en azından) dokunacaktır. Genelliği kaybetmeden, köşesi, , ve köşelerine bir kırmızı kenar ile birleşir diyelim. , ve arasında kırmızı bir çizgi varsa, bunu kullanarak kırmızı bir üçgen oluşturabiliriz. Eğer bu üç yeni nokta arasında hiç kırmızı çizgi yoksa, o zamanda mavi bir üçgen oluşacaktır.
Bu gözlemi kullanarak Ramsey Sayısı ‘yi, içinde köşeli kırmızı bir tam çizge veya köşeli mavi bir tam çizge içermek zorunda olan çizgenin minimum köşe sayısı olarak tanımlıyoruz. Örneğin, yukarıda gördüğümüz gibi olur. Diğer taraftan değerleri büyüdükçe Ramsey Saysı’nın hesaplanması fazlasıyla zorlaşır.
Çok sayıda matematikçiyle ortak çalışma yapmış olmasıyla tanınan Macar matematikçi Erdös, ilginç bir yaklaşım geliştirerek Ramsey Sayısı’na bir alt sınır getirir.
Teorem (Erdös 1947) Eğer ise, o zaman olur. Bunun sonucu olarak olur.
Bu alt sınırı ispatlayabilmek için basit bir olasılık argümanı kullanmak yeterlidir. Bu da bize matematiksel bir soruyu çözerken “değişik ” bir pencereden bakmanın ne kadar güçlü olabileceğini gösterir.
Bu yazı Çizge Teorisi, Kombinatorik içinde yayınlandı ve Erdös, Olasılık, Ramsey Sayısı olarak etiketlendi. Kalıcı bağlantıyı yer imlerinize ekleyin.
94,172 kez ziyaret edildi.