RAMSEY TEORİSİ

Ramsey teorisi, sistemlerde düzen ve örüntü bulmakla ilgilenir. Herhangi bir yapıda belirlenmiş bir özelliğin var olması için en az kaç eleman kullanılmasının yeterli olduğunu araştıran Ramsey Teoremi, kendi adını taşıyan İngiliz filozof ve matematikçi Frank Plumpton Ramsey (1903-1930) tarafından ilk kez ortaya konulmuştur.

Ramsey 1928 yılında mantık üzerine yaptığı çalışmalar sırasında bu soruyu sormuş ve cevap aramıştır. Paul Erdos tarafından üzerine çalışılmış problemin asıl ön plana çıkması için 1960 yıllarının gelmesi gerekmiştir.

Ramsey teorisinin uygulanma alanlarından bir tanesi de güvercin yuvası ilkesidir.

Güvercin yuvası ilkesi;

n tane yuna için n+1 tane güvercininiz varsa en az bir yuvanızda 2 tane veya daha fazla güvercininizolduğu anlamı çıkar.

Ramsey teoreminin ön plana çıkmasını sağlayan problemlerden biri de parti problemidir.

Rastgele seçilmiş kişilerden oluşan 6 kişilik bir partiden en az kaçının birbirini tanıyıp yada tanımadığını garanti edebilir miyiz?

Çözüm için 6 köşe noktamız olsun ve kişilerin birbirini tanıma durumlarını kırmızı çizgi, tanımama durumlarını mavi çizgi ile gösterelim

Her noktanın diğer noktalarla ilişkisi incelendiğinde üç kenarı mavi veya üç kenarı kırmızı olan en az bir üçgenle karşılaşırız.

Ramsey teoremi bu örneklerle sınırlı değildir. Aynı örneği 5 kişinin birbirini karşılıklı tanıdığı ya da 12 kişinin tanımadığı bir partiyi garanti etmek için kaç davetli gerekir. Yani iki değişken için adı geçen özellikleri sağlayan bir sayı bulunur. Böyle sayılara Ramsey Sayıları denir.

Yukarıdaki örnekte de gösterildiği gibi bir çizginin bütün köşe noktaları birbiri ile yalnız ve ancak bir bağ yapıyor ise buna tam çizgi denir ve köşe sayısına göre adlandırılır. Kn, n köşesi olan tam çizgileri gösterir. Yukarıda örnekte olduğu gibi

6 kenarlı ve iki renkli bir düzenli tam çizge çizilirse iki renkten birinde mutlaka bir K3 (üçgen) bulunur.

Bu bir Ramsey sayısıdır ve gösterimi R(3,3)=6 biçiminde gösterilir.

Ramsey Teoremi: n tane renk ve sonsuz tane noktamız olsun. Her iki nokta, bu n renkten bir çizgiyle birleştirilmiş olsun.
O zaman, her iki noktası aynı renk çizgiyle birleştirilmiş sonsuz tane nokta vardır. Bu teoremin çok güzel ve anlaşılır ispatını Ali Nesin hocamız çok güzel yapmıştır. Google da arattığınızda rahatlıkla bulabilirsiniz. Sevgilerimle hoşca kalın.

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 )

Connecting to %s