Ramsey teorisi

Ramsey Kuramı, 20. yüzyılın ilk yarısında yaşamış olan İngiliz matematikçi ve filozof 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 ${\displaystyle a_{0},a_{1},a_{2}...,a_{i},a_{i+1},a_{j+2},...}$ noktası alınır, her ${\displaystyle a_{i}}$ kendisinden sonra gelen ${\displaystyle a_{i+1},a_{i+2},a_{i+3},...}$ noktalarıyla aynı renk çizgiyle (ya hep kırmızı, ya hep mavi çizgiyle) bağlanmıştır. ${\displaystyle a_{0}}$ herhangi bir nokta olsun . ${\displaystyle a_{1},a_{2},a_{3},...}$ noktaları öyle seçilmeli ki, ${\displaystyle a_{0}}$ noktası bu noktalarla hep aynı renk çizgiyle bağlanmış olsun.

${\displaystyle a_{0}}$ 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, ${\displaystyle a_{0}}$’ın aynı renk çizgiyle bağlandığı sonsuz tane nokta vardır. ${\displaystyle a_{0}}$’ın hep aynı renk çizgiyle bağlandığı sonsuz bir nokta kümesi alalım. Bu kümeye ${\displaystyle A_{0}}$ diyelim. Demek ki, ${\displaystyle a_{0}}$, ${\displaystyle A_{0}}$’ın noktalarıyla hep aynı renk çizgiyle bağlanmıştır.

${\displaystyle a_{0}}$ noktasından sonraki ${\displaystyle a_{1},a_{2},a_{3},...}$ noktalarını ${\displaystyle A_{0}}$kümesinden seçelim. Böylece ${\displaystyle a_{0}}$ noktası istenen koşulu sağlar.

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

${\displaystyle a_{2},a_{3},a_{4},...}$ noktaları da ${\displaystyle A_{1}}$ kümesinden seçilir ve böylece yukarıdaki koşul ${\displaystyle a_{1}}$ için sağlanmış olur.

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

${\displaystyle a_{3},a_{4},a_{5}...}$ noktalarını ${\displaystyle A_{2}}$’de seçilir ve böylece yukarıdaki koşul ${\displaystyle a_{2}}$ için sağlanmış olur.

${\displaystyle A_{2}}$’den herhangi bir ${\displaystyle a_{3}}$ noktası alalım. Yukarıda yapılanları ${\displaystyle a_{3}}$ ve ${\displaystyle A_{2}}$ için yapalım. ${\displaystyle A_{2}}$’nin içinde, öyle bir sonsuz ${\displaystyle A_{3}}$ kümesi bulalım ki, ${\displaystyle a_{3}}$, ${\displaystyle A_{3}}$’ün her noktasıyla hep aynı renk çizgiyle bağlanmış olsun. Bunu böylece sonsuza kadar sürdürebiliriz. Demek ki, öyle ${\displaystyle a_{0},a_{1},a_{2},a_{3},a_{4},...,a_{i},a_{i+1},a_{i+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 ${\displaystyle a_{0},a_{1},a_{2},a_{3},...}$ 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 ${\displaystyle a_{0}}$ noktası, kendisinden sonra gelen ${\displaystyle a_{1},a_{2},a_{3},...}$ noktalarıyla hep kırmızı bir çizgiyle bağlanmışsa, ${\displaystyle a_{0}}$ noktası kırmızı noktadır. Eğer ${\displaystyle a_{5}}$ noktası kendisinden sonra gelen ${\displaystyle a_{6},a_{7},a_{8},...}$ noktalarıyla hep mavi çizgiyle bağlanmışsa, ${\displaystyle a_{5}}$ noktası mavi noktadır.

Sonsuz sayıda nokta olduğundan ve yalnızca iki renk olduğundan, ${\displaystyle a_{0},a_{1},a_{2},a_{3},...}$ 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 {${\displaystyle a_{i}}$: ${\displaystyle a_{i}}$ kırmızı bir nokta} ya da {${\displaystyle a_{i}}$: ${\displaystyle a_{i}}$ 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, ${\displaystyle a_{0},a_{1},a_{2},a_{3},a_{4},...}$ noktalarının her birinin kırmızı olduğunu varsaydık. Bu kümeden iki nokta alalım: ${\displaystyle a_{i}}$ ve ${\displaystyle a_{j}}$. i, j’den daha küçük. ${\displaystyle a_{i}}$, kırmızı bir nokta olsun. ${\displaystyle a_{i}}$ noktası ${\displaystyle a_{j}}$noktası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ış ${\displaystyle K_{n}}$ tam çizgesinde ya tamamen A renkli bir ${\displaystyle K_{a}}$ ya da tamamen B renkli bir ${\displaystyle K_{b}}$ 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 ${\displaystyle K_{n}}$ n köşesi olan tam çizgenin gösterimi için kullanılır. ${\displaystyle K_{3}}$ çizgesi bir üçgen belirtir. Tanıma göre 6 kenarlı ve iki renkli bir düzenli tam çizge çizilirse iki renkten birinde mutlaka bir ${\displaystyle K_{3}}$ 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 bilinmiyor. Ramsey sayılarının bulunması çizge kuramının sorularından biridir.

Paul Erdős ve George Szekeres’in teoremi r(a, b) sayılarına üst sınır getiriyor.

Teorem: a≥2 ve b≥2 iki tam sayıysa, r(a, b) ≤ r(a, b-1)+r(a-1, b-a*1) Eğer r(a, b-1) ve r(a-1, b) sayılarının ikisi de çiftse r(a, b) < r(a, b-1)+r(a-1, b).