Ramsey Sayısı

Köşe sayısı n olan tam çizge K_n, 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 köşeli tam bir alt çizge oluştuğunu hangi n değerleri için garanti edebiliriz?

Örneğin n=5 ve k=3 aldığımızda sorumuzun cevabını olumsuz yapacak bir örnek bulabiliyoruz. Aşağıdaki durumda köşe sayısı k=3 olan tek renkli tam bir çizge,  yani kırmızı veya mavi bir üçgen, oluşturmak mümkün değil.

k sayısını sabit tutup, n değerini bir arttırdığımızda cevabın olumlu olacağını görmek çok zor değil. Köşelere v_1, v_2, \ldots, v_6 dersek, her hangi bir köşeye ya üç kırmızı ya da üç mavi kenar (en azından) dokunacaktır. Genelliği kaybetmeden, v_1 köşesi, v_2, v_3, ve v_4 köşelerine bir kırmızı kenar ile  birleşir diyelim. v_2, v_3, ve v_4 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ı R(k,m)‘yi, içinde k köşeli kırmızı bir tam çizge veya m 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 R(3,3) =6 olur. Diğer taraftan k,m 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 {l\choose k}2^{1-{k\choose 2}} < 1 ise, o zaman R(k,k)>l olur. Bunun sonucu olarak R(k,k) > \lfloor 2^{k/2} \rfloor 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.

Reklamlar
Bu yazı Çizge Teorisi, Kombinatorik içinde yayınlandı ve , , olarak etiketlendi. Kalıcı bağlantıyı yer imlerinize ekleyin.

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Connecting to %s