İnsan yaşamı doğal olarak problemlerle doludur. Gündelik yaşamda, sosyal ilişkilerde, teknik konularda, eğitim hayatında ve daha birçok alanda problemlerle karşılaşırız. Dolayısıyla problem çözme becerisi bir insan için temel bir beceridir. Bu temel beceri matematik yapmak için de hayati öneme sahiptir. Hatta bir çokları için matematik problem çözmekten ibarettir. Çoğunlukla geçmiş eğitim yaşantılarındaki matematik, çözülmesi gereken problemlerden oluşan bir alan olarak hatırlanır. Matematik yapmak tamamen problem çözmekten ibaret olmasa da büyük bir bölümünü oluştuğunu söylemek abartı olmayacaktır. Ancak matematikte bazen problem çözmek sadece problem çözmek değildir! Bir problemi çözdükten sonra da matematik yapma süreci devam eder. Bu matematiğin doğasının bir gereğidir. Bir matematikçi bir problemi çözdükten sonra iki şeyi yapmayı sürdürecektir: başka problemlerle ilişkilendirmek ve genellemeye gitmeye çalışmak.
Matematiksel problem çözmenin bu yapısı bazen çığır açıcı gelişmelerin önünü açar. Matematik tarihi bunun ilginç örnekleriyle doludur. Bunlardan en çok bilinenlerinden biri “Königsberg köprüsü problemi”dir. Bu problem hakkında pek çok şey yazılmıştır. Kısaca özetleyecek olursak, 18. yüzyılda Prusya’nın Königsberg şehrinde (şimdi Rusya’ya bağlı Kaliningrad adlı şehir) geleneksel olarak söylene gelen bir problem vardır. Şehirde 7 köprü ve bunlarla birbirine bağlanan 4 mahalle bulunmaktadır. Problem bu köprülerden yalnız bir kez geçerek tüm mahallelerin gezilip gezilemeyeceği üzerinedir. (Problemin ders etkinliği olarak tasarlanmış bir versiyonuna şu linkten ulaşılabilir: https://tr.mathigon.org/course/graph-theory/bridges.) Ünlü matematikçi Euler bu şehre yaptığı bir ziyaret vesilesiyle problemi öğrenir ve söz konusu gezinin imkânsızlığını matematiksel olarak ispatlar.
Euler, problemi çözmekle yetinmemiş ve çözümde kullandığı yöntemi başka problemleri de içerecek şekilde genelleştirmiştir. 1741 yılında bu çalışmalarını "Solutio problematis ad geometriam situs pertinentis (Konum geometrisiyle ilgili bir problemin çözümü)" adıyla yayınlar [1]. Makalenin adından anlaşılacağı üzere, Euler, içinde uzaklık ve ölçü kavramı olmayan ama konumlarla (position) ilgilenen yeni bir geometriden söz etmektedir. Bugün matematikte önemli bir dal olan Çizge Kuramı (Graf Teori)’nın başlangıcı olarak bu makale kabul edilir. Königsberg probleminin çizge kuramına göre modellenmiş hali Şekil 1’de görülmektedir. Burada mahalleler ve köprüler sırasıyla düğümler (node) ve kenarlar (edge) olarak modellenmiştir. Çizge kuramı bu iki temel elemanla (düğüm ve kenar) kurulabilecek modeller hakkındadır. Bilgisayar bilimindeki gelişmelere paralel olarak geniş bir problem alanını kapsayan bir matematik dalı olmuştur. Günümüzde birçok teknik problem (ağ, devre problemleri, ulaşım ve zaman planlaması problemleri gibi) çizge kuramıyla modellenerek çözülebilmektedir [2].
Şekil 1: Königsberg köprüleri ve problemin çizge kuramı modeli ( Kaynak: https://l24.im/U2bYuDI)
Çizge kuramı içinde birçok tanım, kavram, teorem mevcuttur. Bu yazıda çizge kuramını açıklamaya girişilmeyecektir; ancak yazının devamındaki problemle ilgili olacağından basit bir tanıma yer vereceğiz. Bir çizgede tüm düğüm çiftlerini birbirine bağlayan tek bir kenar varsa buna tam çizge adı verilir. n adet düğümden oluşan bir tam çizge şeklinde gösterilir. 2, 3 ve 4 düğümlü tam çizge modelleri şekil 2’de verilmiştir.
Şekil 2
Parti-Tanışma Problemi ve Ötesi
Problem çözmenin ötesine geçmenin az bilinen başka bir örneğine geçelim. Parti-tanışma problemi olarak da bilinen bu problem şöyledir: Diyelim ki bir yılbaşı partisine davetlisiniz ve toplam 6 kişi olacak. Bu kişiler arasında, birbirini hiç tanımayan 3 kişi ya da hepsi birbirini tanıyan 3 kişi olma ihtimali nedir?
Bu problemin başlangıçta tahmin edilmesi güç, şaşırtıcı bir cevabı vardır: Bu ihtimal kesindir! Nasıl olduğunu görmek için çizge kuramını kullanalım. 6 kişiyi düğümlerle (node), tanışma durumunu da kenarlarla (edge) temsil edebiliriz. Bu çizgenin problemimizi ifade edebilmesi için renklendirme kullanalım: İki kişi birbirini tanıyorsa KIRMIZI, tanımıyorsa MAVİ bir kenar ile gösterelim. Örneğin şekil 3’deki gibi bir tam çizge elde edilebilir.
Şekil 3
Örnek çizgeyi incelersek A, B ve D kişilerinin birbirini tanıdığı bir model olduğunu görüyoruz. Problemin cevabının kesin olduğunu göstermek, bu tarz bir modelde her zaman böyle 3 kenarı da kırmızı (ya da 3 kenarı da mavi) olan bir üçgenin oluşmak zorunda olduğunu göstermek demektir. Bunun nasıl olacağını anlamak için çizge modelimize daha yakından bakalım.
Bir köşeyi seçelim (örneğin A). Bu köşeye tam 5 tane kenar geliyor (Şekil 4-I). Bu kenarları 2 renge boyayacağız. Güvercin yuvası ilkesi gereğince [3], 5 nesneyi 2 değişik renge boyadığımızda en az 3 tanesi aynı renk olacaktır. Diyelim ki bu 3 kenar kırmızı olsun (Şekil 4-II). Şimdi bu 3 kenarın diğer köşelerini (B, E ve D) ele alalım. Bu 3 köşeyi birleştiren 3 kenar (yeşil kenarlar) iki farklı renge boyanacak (Şekil 4-III).
Şekil 4
Şekil 4-III’de yeşille gösterilen bu kenarların 3’ü de mavi olursa zaten göstermek istediğimiz sonuç olur. Eğer herhangi biri kırmızı olursa bu defa da kırmızı bir üçgen oluşacağı kesinleşir. Bu durumda problem çözülmüş ve istenen durumun ihtimalinin kesin olduğu görülmüştür.
Şimdi problemin ötesine matematiksel olarak nasıl geçildiğine bakalım. Soruyu ters çevirelim ve şöyle ifade edelim: İçinde 3 kişinin birbirini tanıdığı ya da 3 kişinin birbirini tanımadağı bir grup en az kaç kişiden oluşmalıdır?
Bu sorunun cevabının 6 olduğunu yukarıda göstermiş olduk. Bu durum R(3,3)=6 şeklinde gösterilir. Şimdi bu eşitliği problemin bağlamından çıkararak daha genel şekilde ifade edelim:
R(n,m): İçinde n köşeli kırmızı bir tam çizge veya m köşeli mavi bir tam çizge içermek zorunda olan çizgenin minimum düğüm (köşe) sayısı
Problemin bu genel hali yani n ve m 1’den büyük pozitif tam sayıları için R(n,m) sayısını bulmak, çizge kuramı ile bağlantılı bir kombinatorik problemidir. Örneğin R(2,2)’nin 2’ye eşit olduğu aşikardır. R(n,m)=R(m,n) olduğu sonucuna da kolayca ulaşılabilir. Peki R(4,4) ya da R(5,5) için kolay bir kestirme mümkün müdür? Daha iyi anlaşılması için R(5,5) sayısını ilk probleme uygun olarak ifade edelim: Acaba bir partide birbirini tanıyan ya da hiç tanımayan tam olarak 5 kişinin olmasını garantilemek için partiye en az kaç kişi davet edilmelidir?
R(n,m) sayılarını hesaplama problemi şimdilik bir kenarda dursun. Çok daha genel bir soruya odaklanalım: Acaba R(n,m) sayısı her zaman sonlu mudur? Bu soru ve cevabı bizi bir problemi çözmenin ötesine geçmek anlamında çok daha ileri noktalara götürecektir.
Ramsey Teorisi
20. yüzyılın ilk yarısında yaşamış ve 26 yaşında hayatını kaybetmiş matematikçi Frank Ramsey 1930’da “On a Problem of Formal Logic” [4] adlı bir makale yayınlamıştır ve bu makalede yukarıda ifade edilen R(n,m) sayısının her zaman sonlu olacağının kanıtı yer almaktadır. Problemin genel haline Ramsey sayısı denilmesinin nedeni de bu ispattır [5]. Ramsey’in bu çalışması çizgelerle ilgili bile değildir; matematiksel mantıktaki bir problemle ilgilidir [6]. Ramsey makalesinde esas olarak “Bir yapıda belirlenmiş bir özelliğin var olması için en az kaç eleman kullanılması yeterlidir?” sorusunu temel alan bir teori geliştirmekle ilgilenmiştir. Bu teoriyi geliştirirken bir basamak olarak, R(n,m) sayısının sonlu olduğunun ispatını yapmıştır.
Ramsey, R(n,m) sayısının sonlu olmasından yola çıkarak geliştirdiği teorisi ile belirli örüntülerin kaçınılmaz olarak ortaya çıkması için örneklem evreninin ne kadar büyük olması gerektiğinin niceliksel olarak belirlenebileceğini göstermiştir [6]. Başka bir deyişle, ne kadar karmaşık olursa olsun, büyük bir sistemde her zaman bir tür özel yapı sergileyen daha küçük bir alt sistem vardır [7]. Ramsey sayıları üzerine çalışan matematikçi Benny Sudakov, teorinin temel sonucunun "tamamen kaotik bir sistem yaratılamaz" olduğunu söylemiştir [6]. Königsberg köprüsünden çizge kuramına giden yolda, parti-tanışma probleminden mantık, matematik ve felsefenin konusu olabilecek muazzam bir teoriye varılmıştır. İşte problem çözmenin ötesine geçmek anlamında matematik yapmak!
Ramsey Sayılarını Hesaplamak
R(n,m) sayılarının sonlu olduğunun ispat edilmesi elbette ki bu sayıların araştırılmasını durdurmamıştır. Ancak Ramsey sayılarını hesaplamak hiç de kolay değildir. Bu problem üzerine yapılan çalışmalarda şimdiye kadar bulunabilen R(n,m) sayıları aşağıdaki tabloda görülmektedir.
Tablo 1(Kaynak: Nilüfer Karadağ, Bilim ve Teknik Dergisi, Ağustos 2005, Tübitak.)
Problem çözme ustası bir matematikçi olan Paul Erdös de Ramsey sayıları ile ilgilenmiştir. Erdös bu sayıları hesaplamanın zorluğunu şu şekilde ifade etmiştir:
“Diyelim ki uzaylılar dünyayı istila ediyor ve insanlar R(5,5)’i bulamazsa bir yıl içinde dünyayı yok etmekle tehdit ediyor. Dünyanın en iyi beyinlerini ve en hızlı bilgisayarlarını bir araya getirebilir ve bir yıl içinde muhtemelen değeri hesaplayabiliriz. Ancak uzaylılar R(6,6)’yı talep ederse, önleyici bir saldırı başlatmaktan başka seçeneğimiz kalmaz.” [8]
Ramsey teoreminin ispatlanmasından bu yana geçen yaklaşık 90 yılda, başta Erdös olmak üzere birçok matematikçi R(n,m) sayıları için alt veya üst sınırlar bulmuşlardır [9], [10], [11]; ancak şimdiye kadar kesin bir hesaplama yöntemi bulunamamıştır. Bu konudaki en son gelişme 2023 yılının en önemli matematik olaylarından biri olmuştur. 4 genç matematikçi Mart 2023’de yayınladıkları bir makalede Ramsey sayıları için yeni bir sınır belirlemiştir [6]. Bu gelişme önemli olmakla birlikte Ramsey sayılarını hesaplamak kombinatoriğin açık problemlerinden biri olmaya devam etmektedir.
Ramsey sayılarının sonlu olduğunun ispatı nasıl büyük kapılar açtıysa belki bir gün Ramsey sayılarını bulma probleminin de ötesine geçebilir ve matematikte yeni bir kapı daha açılır. Neden olmasın?
Kaynak:
[1] http://eulerarchive.maa.org/backup/E053.html
[2] https://sitn.hms.harvard.edu/flash/2021/graph-theory-101/
[3] https://bilimgenc.tubitak.gov.tr/makale/guvercin-yuvasi-ilkesi-nedir
[4] https://doi.org/10.1112/plms/s2-30.1.264
[5] https://brilliant.org/wiki/ramsey-theory/
[6] https://www.quantamagazine.org/after-nearly-a-century-a-new-limit-for-patterns-in-graphs-20230502/
[7] https://math.mit.edu/~fox/MAT307-lecture05.pdf
[8] https://www.scientificamerican.com/blog/roots-of-unity/moores-law-and-ramsey-numbers/
[9] Burling, J. P. and Reyner, S. W. "Some Lower Bounds of the Ramsey Numbers n(k,k)." J. Combin. Th. Ser. B 13, 168-169, 1972.
[10] Erdös, P., & Faudree, R.J. (1989). On the Difference between Consecutive Ramsey Numbers.
[11] Chung, F. and Grinstead, C. G. "A Survey of Bounds for Classical Ramsey Numbers." J. Graph. Th. 7, 25-37, 1983.




