Arkadaşlar ve Yabancılar: Ramsey Teoreminin Basit Bir Grafik Kanıtı
Frank Ramsey, 1903'te İngiltere'nin Londra kentinde doğdu ve daha sonra matematik eğitimi almak için Trinity College of Cambridge Üniversitesi'ne girdi ve olağanüstü bir matematikçi, filozof ve ekonomist oldu. Tian'ın yetenekleri kıskanması ve 1930'da Londra'da ölmesi üzücü. Ancak kısa sürede matematik ve diğer alanlarda pek çok katkı yaptı. Bugün konuşacağımız şey Ramsey'in 1930'da yayınlanan "Biçimsel Mantıkta Bir Sorun" adlı makalesinde önerdiği teoremidir.
Ramsey Teoremi (Ramsey Teoremi), grafik teorisinde önemli bir kavramdır.N adet köşeli tam bir grafik olarak ifade edilir.Tüm köşeler kırmızı veya mavi çizgilerle birbirine bağlanabilir. Tümü kırmızı veya tümü mavi olmak üzere tamamen aynı olan büyük bir alt kümeyi sunacaktır. Önce tutarlı alt kümenin boyutunu da belirleyebilir ve ardından alt kümeyi Ramsey teoremine göre oluşturmak için gereken tüm grafiği tersine çevirebiliriz.
Tam bir grafik, çiftler halinde birbirine bağlı tüm köşelerden oluşan bir grafiği ifade eder. (Resim kaynağı: Lucy Reading-Ikkanda / QuantaMagazine)
Ramsey teoreminin "Dostluk Teoremi" adlı basit ve anlaşılması kolay bir versiyonu da vardır: Altı kişiden en az üçü birbirini tanıyor (arkadaşlar) veya birbirini tanımıyor (yabancılar) . Ama bu teorem neden doğru? Resmin tamamındaki bu farklı renkli çizgiler neden tamamen bozulamıyor? Matematikçi Jonathan Jedwab, bu teoremin neden doğru olduğunu sezgisel olarak açıklamak için bir dizi grafik kullandı.
Basit bir örneğe bakalım - tam bir altıgen grafik, aynı renkte en az üç çizgiden oluşan bir alt küme oluşturabilir. Bu neden?
Bu altı maddeye altı kişi olarak bakıldığında, bunlardan herhangi biri ve diğeri bilmek ya da bilmemek durumunda olmalıdır. Olursa, ikisini kırmızı kabloyla, yoksa mavi kabloyla bağlarız. Bu nedenle, bu küçük sosyal çevrede, herkes diğer beş kişiyle bağlantı kurmak için beş çizgi yayar ve en az üçü aynı renge sahiptir. Bu, bu insanları nasıl birleştirirseniz birleştirin, sonucun tamamen kırmızı veya tamamen mavi bir üçgen olacağı anlamına gelir.
(Resim kaynağı: QuantaMagazine)
Öncelikle 1'e bakalım. Kendisinden başlatılan beş çizgi arasından en az üç çizgi daha önce bahsedildiği gibi aynı renge sahip. 2, 4 ve 5'i biliyorsa bu üç çizgi kırmızıdır.
(Resim kaynağı: QuantaMagazine)
Tekrar 2 ve 5'e bakın, 2 ile 5 karşılaşıyorsa 2 ile 5 arasındaki çizgi de kırmızı olur ve kırmızı bir üçgen elde edilir. Bakalım bu tür üçgenlerden kaçınmanın bir yolu var mı, bu yüzden 2 ve 5'in birbirini tanımadığını varsayın ve 2 ile 5 arasındaki mavi çizgiyi işaretleyin.
(Resim kaynağı: QuantaMagazine)
Sonra, 4 ile 5 arasındaki ilişkiyi göz önünde bulundurun. Benzer şekilde, 1, 4 ve 5'in kırmızı bir üçgen oluşturmasını önlemek için, 4 ile 5'in birbirini tanımadığını varsayıyoruz.
(Resim kaynağı: QuantaMagazine)
Son olarak 2 ile 4 arasındaki ilişkiye bakıldığında 4 Şubat'ta tanışsınlar ya da tanışmasınlar kırmızı veya mavi bir üçgen oluşacağı ortaya çıkıyor. Daha sonra bir dizi küçük tek renkli renk yaması görünecek ve Ramsey teoremi doğrulanacaktır.
(Resim kaynağı: QuantaMagazine)
Milyonlarca, on milyonlarca ve yüz milyonlarca insan gibi daha geniş bir koleksiyondaki örnekleri incelemek için bu yöntemi kullanırken, tek renkli renk grubunun aynı renkten çok sayıda çizgiden oluştuğunu görebilirsiniz. Ama bu "kütle" ne kadar büyük? Matematikçiler emin olamaz. Tek renkli bir alt kümenin boyutu bilinene kadar, onu oluşturmak için gereken tüm grafiğin minimum boyutunu bilemeyiz.
Ramsey teoremi, günlük olarak kullanılan diğer birçok araç gibi - oldukça kullanışlıdır, ancak arkasındaki tüm çalışma prensiplerini tam olarak anlamıyoruz.
