Ramsey Kuramı-Ramsey Teoremi

Ramsey Kuramı


Ramsey Kuramı, 20 yüzyılın ilk yarısında yaşamış olan İngiliz matematikçi Frank Ramsey, adını taşıyan ve ‘bir yapıda belirlenmiş bir özelliğin var olması için en az kaç eleman kullanılması yeterlidir’ sorusunu temel alan bir teori Ramsey kuramının sorularından biri; bir odadaki sonsuz tane insanın ya hepsinin birbirini tanıması ya da hiçbirinin birbirini tanımamasıdır

Ramsey teoremi

n sayıda renk ve sonsuz sayıda noktamız olsun Her iki nokta, bu n renkten birine boyanmış bir kenarla birleştirilmiş olsun O zaman, bütün noktaları aynı renk kenarla birleştirilmiş sonsuz tane noktadan oluşan bir küme vardır Her insan bir nokta olarak gösterilsin Eğer iki insan birbirini tanıyorsa, bu iki insanı birbirine kırmızı bir çizgiyle bağlayalım Eğer iki insan birbirini tanımıyorsa, bu iki insanı da mavi bir çizgiyle bağlayalım Her ikisi kırmızı ya da mavi çizgiyle birleştirilmiş sonsuz tane nokta elde edilir Bu noktalar arasından, hep aynı renkle (ya hep kırmızıyla ya hep maviyle) birleştirilmiş sonsuz tane nokta bulunabilir

Kanıt

Kanıt,iki aşamada gerçekleşir Birinci aşamada , sonsuz tane a0,a1,a2,ai,ai + 1,aj + 2, noktası alınır , her ai kendisinden sonra gelen ai + 1,ai + 2,ai + 3, noktalarıyla aynı renk çizgiyle (ya hep kırmızı, ya hep mavi çizgiyle) bağlanmıştır a0 herhangi bir nokta olsun a1,a2,a3, noktaları öyle seçilmeli ki, a0 noktası bu noktalarla hep aynı renk çizgiyle bağlanmış olsun

a0 noktası, (kişileri simgeleyen) öbür noktalarla ya kırmızı ya da mavi bir çizgiyle bağlanmıştır Sonsuz tane nokta olduğundan ve yalnızca iki tane bağlantı rengi olduğundan, a0’ın aynı renk çizgiyle bağlandığı sonsuz tane nokta vardır a0’ın hep aynı renk çizgiyle bağlandığı sonsuz bir nokta kümesi alalım Bu kümeye A0 diyelim Demek ki, a0, A0’ın noktalarıyla hep aynı renk çizgiyle bağlanmıştır

a0 noktasından sonraki a1,a2,a3, noktalarını A0kümesinden seçelim Böylece a0 noktası istenen koşulu sağlar

A0’dan herhangi bir a1 noktası alalım a1 noktası, A0’ın öbür noktalarına ya kırmızı ya da mavi bir renkle bağlanmıştır A0’da sonsuz tane nokta olduğundan ve yalnızca iki rengimiz olduğundan, A0 kümesinde, a1’in aynı renk çizgiyle bağlandığı sonsuz tane nokta vardır Yani, ya {a∈A0: a1 noktası a’yla kırmızı bir çizgiyle bağlanmış} kümesi , ya da {a∈A0: a1 noktası a’yla mavi bir çizgiyle bağlanmış } kümesi sonsuzdur Bu kümelerden sonsuz olanına A1 diyelimDemek ki , a1 , A1’in noktalarıyla hep aynı renk çizgiyle bağlanmıştır

a2,a3,a4, noktaları da A1 kümesinden seçilir ve böylece yukarıdaki koşul a1 için sağlanmış olur

A1’den herhangi bir a2 noktası alalım a2 noktası A1’in öbür noktalarıyla ya kırmızı ya da mavi bir çizgiyle bağlanmıştır A1’de sonsuz nokta olduğundan ve yalnızca iki rengimiz olduğundan, A1’de, a1’in hep aynı renkle bağlandığı sonsuz tane nokta vardır Bir başka deyişle, ya {a∈A1: a2 noktası a’yla kırmızı bir çizgiyle bağlanmış} kümesi, ya da {a∈A1: a2 noktası a’yla mavi bir çizgiyle bağlanmış} kümesi sonsuzdur Bu kümelerden sonsuz olanına A2 diyelim Demek ki, a2, A2’nin noktalarıyla hep aynı renk çizgiyle bağlanmıştır

a3,a4,a5 noktalarını A2’de seçilir ve böylece yukarıdaki koşul a2 için sağlanmış olur

A2’den herhangi bir a3 noktası alalım Yukarıda yapılanları a3 ve A2 için yapalım A2’nin içinde, öyle bir sonsuz A3 kümesi bulalım ki, a3, A3’ün her noktasıyla hep aynı renk çizgiyle bağlanmış olsunBunu böylece sonsuza kadar sürdürebiliriz Demek ki, öyle a0,a1,a2,a3,a4,,ai,ai + 1,ai + 2,noktaları bulunur ki, her nokta kendisinden sonra gelen noktalarla aynı renk çizgiyle bağlanmış olur

Kanıtın birinci aşaması tamamlandı İkinci aşama:

Seçilen a0,a1,a2,a3, noktalarının her birine bir renk verilir Eğer bir nokta kendisinden sonra gelen noktalarla hep kırmızı çizgiyle bağlanmışsa, o noktaya kırmızı nokta diyelim Yoksa, o noktaya mavi nokta diyelim Örneğin, eğer a0 noktası, kendisinden sonra gelen a1,a2,a3, noktalarıyla hep kırmızı bir çizgiyle bağlanmışsa, a0 noktası kırmızı noktadır Eğer a5 noktası kendisinden sonra gelen a6,a7,a8, noktalarıyla hep mavi çizgiyle bağlanmışsa, a5 noktası mavi noktadır

Sonsuz sayıda nokta olduğundan ve yalnızca iki renk olduğundan, a0,a1,a2,a3, noktalarından sonsuz tanesi aynı renk noktadır Bir başka deyişle, ya kırmızı noktalar kümesi ya da mavi noktalar kümesi sonsuzdur Matematiksel olarak , ya {ai: ai kırmızı bir nokta} ya da {ai: ai mavi bir nokta} kümesi sonsuzdur İki küme birden de sonsuz olabilir, ama en azından birinin sonsuz olduğunu biliyoruz İki kümeden sonsuz olanını alalım Öbür noktaları atalım Noktaları yeniden adlandırarak, her noktanın aynı renk olduğunu varsayalım , hepsi kırmızı olsun Demek ki, a0,a1,a2,a3,a4, noktalarının her birinin kırmızı olduğunu varsaydık Bu kümeden iki nokta alalım: ai ve aj i, j’den daha küçük ai, kırmızı bir nokta olsun ai noktası ajnoktasıyla kırmızı bir çizgiyle bağlanır Demek ki yukarıdaki sonsuz nokta birbirleriyle aynı renk çizgiyle (kırmızıyla) bağlanmıştır Ramsey’in teoremi kanıtlanmış oldu

Ramsey sayıları

Teorem: a ve b herhangi iki doğal sayı olsunÖyle bir N vardır ki , eğer n≥N ise , kenarları A ve B renklerine boyanmış Kn tam çizgesinde ya tamamen A renkli bir Ka ya da tamamen B renkli bir Kb vardır

Tanım: Eğer bir çizgenin bütün köşe noktaları birbiri ile yalnız ve ancak bir bağ yapıyorsa bunlara tam çizgeler denir ve köşe noktası sayısına göre adlandırılırÖrneğin Kn n köşesi olan tam çizgenin gösterimi için kullanılırK3 çizgesi bir üçgen belirtirTanıma göre 6 kenarlı ve iki renkli bir düzenli tam çizge çizilirse iki renkten birinde mutlaka bir K3 bulunur

Teoremde en küçük N sayısına Ramsey sayısı denir ve r(a,b) olarak yazılır

Yukarıdaki örnek r(3,3)=6 olur

Bazı r(a,b) sayılarını bulmak kolay ; r(1,b)=1 r(2,b)=b Ramsey sayıları için genel bir formül bilinmiyorRamsey sayılarının bulunması çizge kuramının sorularından biridir

Erdös ve Szekeres’in teoremi r(a,b) sayılarına üstsınır getiriyor

Teorem: a≥2 ve b≥2 iki tamsayıysa , r(a,b) ≤ r(a,b-1)+r(a-1,b) Eğer r(a,b-1) ve r(a-1,b) sayılarının ikiside çiftse r(a,b) < r(a,b-1)+r(a-1,b)