Türkçe Bilgi logo TürkçeBilgi

Ramsey Kuramı

Kısaca: 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. ...devamı ☟

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 a_0, a_1, a_2 ... ,a_i, a_, a_ ,... noktası alınır , her a_i kendisinden sonra gelen a_, a_, a_,... noktalarıyla aynı renk çizgiyle (ya hep kırmızı, ya hep mavi çizgiyle) bağlanmıştır. a_0 herhangi bir nokta olsun . a_1, a_2, a_3,... noktaları öyle seçilmeli ki, a_0 noktası bu noktalarla hep aynı renk çizgiyle bağlanmış olsun. 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, a_0’ın aynı renk çizgiyle bağlandığı sonsuz tane nokta vardır. a_0’ın hep aynı renk çizgiyle bağlandığı sonsuz bir nokta kümesi alalım. Bu kümeye A_0 diyelim. Demek ki, a_0, A_0’ın noktalarıyla hep aynı renk çizgiyle bağlanmıştır. a_0 noktasından sonraki a_1, a_2, a_3,... noktalarını A_0 kümesinden seçelim. Böylece a_0 noktası istenen koşulu sağlar. A_0’dan herhangi bir a_1 noktası alalım. a_1 noktası, A_0’ın öbür noktalarına ya kırmızı ya da mavi bir renkle bağlanmıştır. A_0’da sonsuz tane nokta olduğundan ve yalnızca iki rengimiz olduğundan, A_0 kümesinde, a_1’in aynı renk çizgiyle bağlandığı sonsuz tane nokta vardır. Yani, ya kümesi , ya da kümesi sonsuzdur. Bu kümelerden sonsuz olanına A_1 diyelim.Demek ki , a_1 , A_1’in noktalarıyla hep aynı renk çizgiyle bağlanmıştır. a_2, a_3, a_4,... noktaları da A_1 kümesinden seçilir ve böylece yukarıdaki koşul a_1 için sağlanmış olur. A_1’den herhangi bir a_2 noktası alalım. a_2 noktası A_1’in öbür noktalarıyla ya kırmızı ya da mavi bir çizgiyle bağlanmıştır. A_1’de sonsuz nokta olduğundan ve yalnızca iki rengimiz olduğundan, A_1’de, a_1’in hep aynı renkle bağlandığı sonsuz tane nokta vardır. Bir başka deyişle, ya kümesi, ya da kümesi sonsuzdur. Bu kümelerden sonsuz olanına A_2 diyelim. Demek ki, a_2, A_2’nin noktalarıyla hep aynı renk çizgiyle bağlanmıştır. a_3, a_4, a_5... noktalarını A_2’de seçilir ve böylece yukarıdaki koşul a_2 için sağlanmış olur. A_2’den herhangi bir a_3 noktası alalım. Yukarıda yapılanları a_3 ve A_2 için yapalım. A_2’nin içinde, öyle bir sonsuz A_3 kümesi bulalım ki, a_3, A_3’ün her noktasıyla hep aynı renk çizgiyle bağlanmış olsun.Bunu böylece sonsuza kadar sürdürebiliriz. Demek ki, öyle a_0, a_1, a_2, a_3, a_4, ..., a_i, a_, a_,... 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 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 a_0 noktası, kendisinden sonra gelen a_1, a_2, a_3,... noktalarıyla hep kırmızı bir çizgiyle bağlanmışsa, a_0 noktası kırmızı noktadır. Eğer a_5 noktası kendisinden sonra gelen a_6, a_7, a_8,... noktalarıyla hep mavi çizgiyle bağlanmışsa, a_5 noktası mavi noktadır. Sonsuz sayıda nokta olduğundan ve yalnızca iki renk olduğundan, 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 ya da 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, 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: a_i ve a_j. i, j’den daha küçük. a_i, kırmızı bir nokta olsun. a_i noktası 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ış K_n tam çizgesinde ya tamamen A renkli bir K_a ya da tamamen B renkli bir 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 K_n n köşesi olan tam çizgenin gösterimi için kullanılır.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 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. 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-a*1) 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).

Kaynaklar

Vikipedi

Bu konuda henüz görüş yok.
Görüş/mesaj gerekli.
Markdown kullanılabilir.

Ramsey teorisi
3 yıl önce

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...
Teorİ
3 yıl önce

Bilgi kuramı Film: Film kuramı Jeoloji: Plaka tektoniği Sosyal bilimler: Eleştirel kuram Edebiyat: Edebiyat teorisi Matematik: Olasılık kuramı — Arakelov...

Kuram, Bilim, Bilim felsefesi, Deney, Evrim kuramı, Görelilik kuramı, Hipotez, Kanun, Kuantum kuramı, Yapısalcılık, İlke
Tenzing Norgay
3 yıl önce

İngiliz George Madalyası'nın da bulunduğu çok sayıda nişan verildi. James Ramsey Ullman'la birlikte hazırladığı Man of Everest (Everest Adamı) (1955) adlı...

Tenzing Norgay, 1914, 1953, 1986, 29 Mayıs, 9 Mayıs, Edmund Hillary, Everest Dağı, Kişi, Nepal, Taslak
Trabzonspor 2008-09 sezonu
3 yıl önce

firmasıyla 3+2 yıllık sözleşme imzalandı. Giyim sponsorluğu için ise Ramsey'le anlaşıldı. Ayrıca Değirmenderespor'un adı değiştirilerek Trabzon Karadenizspor'a...
Genelliği kaybetmeden
7 yıl önce

ispatın tüm kümede geçerli olup olmayacağına bakarız. Aşağıdaki kuramı inceleyelim (Ramsey'in kuramının en basit hali ve ayrıca Dirichlet'in güvercin yuvası...

Genelliği kaybetmeden, Dirichlet, Kuram, Matematik, Permütasyon, Varsayım, í–nerme, Ramsey`in kuramı, Güvercin yuvası ilkesi, Matematiksel jargon, İspat
Ekonomistler listesi
3 yıl önce

Christopher A. Pissarides Edward Prescott Francois Quesnay Frank Plumpton Ramsey Daniel Raymond George Reisman David Ricardo Lionel Robbins Abraham Robinson...

Ekonomistler listesi, Adam Smith, Alan Greenspan, Arthur Cecil Pigou, Arthur Melvin Okun, Bertil Ohlin, Daniel Kahneman, David Ricardo, Frederic Bastiat, Friedrich Engels, Jan Tinbergen
Thomas Gainsborough
3 yıl önce

eserleri sergilenmeden geri çekti. 1784'te "Kraliyet Resmi Ressamı" olan Allan Ramsey öldü. Yeni kraliyet ressamı olarak Gainsborough'nun portre çiziminde rakibi...
2016 Avrupa Futbol Şampiyonası
3 yıl önce

Admir Mehmedi Fabian Schär Xherdan Shaqiri Ozan Tufan Burak Yılmaz Aaron Ramsey Neil Taylor Sam Vokes Ashley Williams 1 kendi kalesine Birkir Már Sævarsson...