Uygulamalı Matematik

Ramsey Teorisi: Kehanetlerin Ardındaki Matematik

Dönem dönem belli kitaplarda şifreler ya da kehanetler olduğunu söyleyen insanlar ortaya çıkar. Bir biçimde bu şifreleri incelediğimizde inanmak istemesek de aklımıza oldukça yatkın olduğunu görürüz. Ancak düzensiz sistemlerde her zaman bir düzen bulabiliriz. Ramsey teorisi, sistemlerde düzen ve örüntü bulmakla ilgilenir.

Ramsey teorisi, İngiliz matematikçi ve filozof Frank Plumpton Ramsey (1903-1930) adını taşır. Bir yapıda belli bir özelliğin var olması için en az kaç eleman kullanılması yeterlidir? sorusunu temel alır. Ramsey’in 1928’de mantık üzerine çalışmalar yaparken Ramsey’in sezgisel olarak düşündüğü bu teorinin günümüzde birçok uygulama alanı vardır. Teorinin temel fikirlerini anlamak oldukça kolaydır. Öte yandan, bazı olağanüstü zor soruları gündeme getirdiği için aynı zamanda aktif bir araştırma alanıdır. Ancak Paul Erdos’un bazı ilginç çalışmaları dışında Ramsey teorisi ile ilgili araştırmalar 1950’lerin sonlarına kadar başlamamıştır.

Frank Plumpton Ramsey İngiliz filozof, matematikçi ve ekonomist. 26 yaşında ölümünden önce her üç alana önemli katkıları olmuştur. 

Ramsey teorisinin sorduğu temel soru şudur. Düzensiz ve karmaşık bir sistemde her zaman bir düzen var mıdır? Eğer öyleyse, içinde belirli bir düzen bulabileceğimizden emin olmak için düzensizliğin boyutu ne olmalıdır? Bu sorular size garip geldiyse somut bir örnek sunalım. İçinde altı kişinin olduğu bir oda olduğunu varsayalım. Bu odadaki insanların birbirlerini tanıyıp tanımadıklarıyla ilgileniyoruz. İki kişi birbirini tanıyorsa arkadaş, tanımazlarsa yabancı diyelim.

Düzensizlikten Düzene Geçiş

Kuşkusuz en düzenli durum, altı kişinin ya tamamen arkadaş ya da tamamen yabancı olması olurdu. Ancak insanlar rastgele seçildiği için muhtemelen odada arkadaş ve yabancılar karışık biçimde olacaktır. Odadaki her bir insan çiftini birleştiren çizgiler çizdiğimizi ve ikisi arkadaşsa maviye, yabancıysa kırmızıya boyadığımızı varsayalım. Grafik oldukça karışık gözüküyor. Ama yine de odada en azından hepsi arkadaş ya da tamamen yabancı olan üç kişiyi bulabilir miyiz?

Şaşırtıcı bir şekilde, oradaki üçer kişiden oluşan bir grupta, ya herkesin birbirini tanıdığından ya da daha önce tanışmadıklarından emin olabiliriz. Şekle baktığınız zaman üç kenarı mavi ve 3 kenarı kırmızı olan üçgenler göreceksiniz. 6 kişide en az bir tane böyle bir üçgen bulmak mümkündür. Örneğin bu rastgele çizili grafiğimizde ( çizgemizde) Charlie, Evelyn ve Fred birbirlerine yabancıdırlar. Çünkü bu üçlünün oluşturduğu üçgenin üç kenarı da kırmızıdır.

Kağıt ve renkli kalemlerle denemeler yapmak, altı kişiyle her zaman tek renkli bir üçgen olduğuna bizi ikna edecektir. Ancak ikna olmak yetmez. Bunun doğru olduğunu nasıl kanıtlayacağız? Bunun bir yolu, olası tüm seçenekleri listelemek ve sırayla her birini kontrol etmek olacaktır. Ne yazık ki 30.000’den fazla olası seçenek olduğu düşünülünce bu biçimde bir kanıt yapmak fazla da eğlenceli değildir. Neyse ki, bunu çok daha kolay kanıtlayabiliriz.

Bir nokta düşündüğümüzde bundan beş tane çizgi çıkmalıdır. Bu beş çizgide bir renkten en az üç tane olmalıdır. Yani bir noktadan çıkan en az üç kırmızı çizgi veya en az üç mavi çizgi vardır. Diyelim ki üç kırmızı çizgi var. Kalan üç çizgi hangi renklerde olacaktır? Bunlardan biri bile kırmızı olursa A noktası (solda) ile birlikte kırmızı bir üçgen oluşturur. Aksi halde üçü birlikte mavi bir üçgen oluşturacaktır.(sağda).

Ramsey Sayıları

Yukarıda altı noktayla her zaman tek renkli bir üçgen olması gerektiğini kanıtladık. Diğer bir deyişle,” Üçünün arkadaş ya da üçünün yabancı olduğundan emin olmak için en az kaç kişiye ihtiyacımız var?” sorusunun cevabını bulduk. Bu bizim ilk Ramsey sayısı örneğimizdir ve R(3,3)olarak yazılır. Altı kişinin kesinlikle yeterli olduğunu gördük; başka bir deyişle, R(3,3) 6’dan büyük değildir. Aynı zaman da 6’dan da küçük olamaz. Bunu anlamak için aşağıdaki grafiğe göz atın. Gördüğünüz gibi beş kişi ile böyle bir sonuca ulaşmak mümkün değildir. Bu durumda R(3,3)=6 olmalıdır.

5 noktalı grafikte üç kenarı aynı renk olan bir üçgen bulmak mümkün değildir.

Şimdi başka bir Ramsey sayısı ile uğraşalım. R(4,4) ifadesi bize ya 4 ortak arkadaş ya da 4 ortak yabancı bulma konusunda emin olmak için kaç kişiye ihtiyaç olduğunu söyler. Bunu hesaplamak kolay değil. Bu nedenle işe R(3,4)’ü bularak başlayalım. Yani “hepsi mavi çizgilerle birbirine bağlı üç nokta, ya da hepsi kırmızı çizgilerle bağlı dört nokta bulmayı garanti etmek için kaç noktaya ihtiyacımız var?” sorusunun cevabını arayalım. Bu yukarıda aktardığımız ispata benzer bir biçimde yapılır (İspatı burada vermeyeceği, merak edenler kaynağı inceleyebilir). Bunun sonucunda da R(3,4)=9 bulunur. Şimdi bu bilgiyi R(4,4) bulmak için kullanabiliriz.

İlk olarak, dört arkadaş veya dört yabancıyı garanti etmek için 18 kişinin yeterli olduğunu iddia edelim. Bir nokta alalım ve 17 çizgi çizelim. Bu çizgilerden en az 9 tanesi aynı renk olmalıdır. R(4,3)=9 olduğunu zaten biliyoruz. Yani bu 9 nokta arasında ya dört arkadaş ya da üç yabancı olmalıdır. Üç yabancı varsa, A’da bu kişilere yabancı olduğundan toplam dört yabancımız var. Yani ya dört arkadaşımız ya da dört yabancımız var. Bu da iddia ettiğimiz şeydir. R(4,4) kesinlikle vardır ve en fazla 18’dir. Ayrıca 17 nokta da böyle bir kümeyi oluşturmak için yeterli değildir. ( Neden derseniz ispatı oldukça uzun ve burada). Sonuç olarak R(4,4)=18’dir.

Daha Büyük Ramsey Sayıları

Yukarıda R(3,4) ve R(4,3) için sınır koyabildiğimiz zaman R(4,4)’ü hesaplayabileceğimizi anlatmaya çalıştık. Aslında R(3,3) ve R(2,4)’e sınır koyabildiğimiz zaman R(3,4)’ü hesaplayabiliriz. Matematiksel gösterimde, hem R(a-1,b) hem de R(a,b-1) var olduğu sürece R(a,b)’nin var olduğunu bulabiliriz. Bu ilişkiyi aşağıda görebilirsiniz. Bu mantıkla R(5,5), R(6,6) ve diğer Ramsey sayıları mevcut olmalıdır. Bu Ramsey teorisidir. Bize verilen grafik yeterince büyük olduğu sürece istediğimiz düzeni bulabileceğimizi söyler.

Peki R(5,5)’in değeri nedir? Kimse bilmiyor! Aslında, çok az sayıda Ramsey R(a,b) sayısı bilinmektedir. R(3,3)=6, R(4,3)=9 ve R(4,4)=18, R(5,3)=14, R(6,3)=18 ve R(7,3)=23 bildiklerimizdir. Mevcut bilgilerimizle R(5,5) hakkında söyleyebileceğimiz en fazla şey, 42 ile 55 arasında bir yerde olduğudur.

Kaynak ve ileri okumalar için: Imre Leader; Friends and strangers; https://plus.maths.org/

Matematiksel

Sibel Çağlar

Merhabalar. Matematik öğretmeni olarak başladığım hayatıma 2016 yılında kurduğum matematiksel.org web sitesinde içerikler üreterek devam ediyorum. Matematiğin aydınlık yüzünü paylaşıyorum. Amacım matematiğin hayattan kopuk olmadığını kanıtlamaktı. Devamında ekip arkadaşlarımın da dahil olması ile kocaman bir aile olduk. Amacımıza da kısmen ulaştık. Yolumuz daha uzun ama kesinlikle çok keyifli.
Başa dön tuşu