Ramsey Teorisi, Karmaşık Sayı Düzenlemeleri Yoluyla Sıralama Yaparken Kaostan Sırayı Çıkarıyor


Altı kişilik küçük bir partiye ev sahipliği yaptığınızı ve kimin birbirini tanıyıp kimin tanımadığının anlaşılmadığını hayal edin. Görünüşe göre, birbirine tamamen yabancı olan en az üç kişi ya da zaten arkadaş olan üç kişi var. (Arkadaşlarınızın birbirinden hoşlanmadığını varsaymıyoruz.) Bu yüzden her zaman birbirini tanıyan ya da hiç tanımayan en az üç kişilik bir grup olacaktır.

Bu ilk başta çok şaşırtıcı gelmeyebilir, ancak sorun hakkında ne kadar çok düşünürseniz, o kadar ilgi çekici hale gelir. Altı kişinin birbiriyle 15 bağlantısı var. Öyleyse, A kişisinin B kişisiyle nasıl bir ilişkisi olduğunu sorabilirsiniz. A, C kişisiyle nasıl ilişkilidir? B, C’yi biliyor mu? Bu bağlantılar iki değerden birine sahip olabilir: arkadaşlar veya yabancılar. Bu, yalnızca altı misafirle zaten 2 kişi olduğu anlamına gelir.15 (32.768) partiye katılanların birbirleriyle ilişki kurabilecekleri farklı yollar. Ve matematik, her olası gruplandırmada, her zaman herkesin birbirini tanıdığı ya da tamamen yabancı olduğu bir üçlü olduğunu iddia ediyor. Her bir vakayı tek tek incelemek ve bir üçlü aramak oldukça zahmetli görünüyor.

Aslında, bunu anlamak, 26 yaşında trajik bir şekilde genç yaşta ölen İngiliz matematikçi Frank Ramsey’in (1903–1930) adını taşıyan Ramsey teorisinin kapsamına giriyor. kaos içinde belirli bir düzeni belirlemekle ilgilenir. Amaç, parti müdavimlerimizin durumunda olduğu gibi, kafa karıştırıcı düzenlemelerde yinelenen kalıpları tanımaktır. Soru matematiksel bir bakış açısıyla çerçevelenebilir: Birbirini tanıyan en az üç kişilik bir grup veya üç tamamen yabancı en az bir grup olması için kaç misafir davet etmeniz gerekiyor?

Her şey, nokta ağları (düğümler olarak da adlandırılır) ve kenarlar (noktaları birleştiren çizgiler) olan şekiller veya grafiklerle çözülebilir. Her kişi bir düğümü sembolize eder. Altı konuk bir daire şeklinde düzenlenebilir. Şimdi her nokta birbirine bağlı. Bu 15 kenar oluşturur. İki kişinin birbirini tanıyıp tanımadığına bağlı olarak kırmızı (tanıdıklar için) veya mavi (yabancılar için) renklidir. Şimdi iddia: Kenarları nasıl renklendirdiğiniz önemli değil, her zaman tek renkli bir üçgen elde edersiniz – tamamen mavi veya tamamen kırmızı bir şekil.

Şimdi ek iddia Ramsey teorisine göre yapılmıştır: Az önce bahsedilen altı konukla, kenarları nasıl renklendirirseniz renklendirin, her zaman en az bir monokromatik üçgen elde edersiniz -tamamen mavi veya tamamen kırmızı bir figür. Denerseniz, böyle bir üçgenin her zaman göründüğünü göreceksiniz.

Tabii ki, kimse 32.768 olasılık arasında dolaşmak istemez. Ve bunu yapmak, Ramsey’in, kaçınılmaz olarak böyle bir üçgen oluşturacak en küçük misafir sayısının altı olup olmadığına ilişkin bir soruyu yanıtlamaz. Davet edilen kişi sayısını değiştirerek bu sorunu çözmeyi deneyebilirsiniz. Hiçbir tek renkli üçgen görünmeyecek şekilde renkli üçgenler bulursanız, aksini kanıtlamışsınızdır. Sadece üç misafir davet etseniz, iki kişi daha önce tanışabilirdi. Yani bu durumda, hepsi bilinen ya da birbirine yabancı olan üç insan yoktur – dolayısıyla tek renkli bir üçgen yoktur.

Üçgen
Spektrum der Wissenschaft/Manon Bischoff

Dört kişiyle, hiç tanımadıkları ya da birbirleriyle arkadaş olan üç kişilik bir grubun olmadığı durumları bulmak da kolaydır.

Bir X oluşturan iki ikiye bölen çizgi ile kare.
Spektrum der Wissenschaft/Manon Bischoff

Beş misafirle bile, aynı renkte bir üçgen olmadan en az bir arkadaş-yabancı bağlantısı konfigürasyonu vardır. Dolayısıyla, Ramsey’in ilişkileri her zaman en az bir tek renkli üçgenle gösterilebilen en küçük partiye katılanlar grubu hakkındaki sorusunu yanıtlamak için sayı beşten fazla olmalıdır. Ama daha ne kadar?

Pentagram oluşturan beş ikiye bölen çizgili Pentagon.
Spektrum der Wissenschaft/Manon Bischoff

Altı kişiye ulaştığımızda ne olur? Şimdi tek renkli bir üçgen oluşturmadan grafiğin kenarlarını renklendirmeye çalışmalısınız. Bunu yapmak için önce tek bir A kişisini seçebilir ve diğer konuklarla ilişkisinin ne olduğunu inceleyebilirsiniz. Diyelim ki A kişisi partinin hostesi. Davetliler arasında kaç arkadaşı var? Onu beş misafire bağlamanın altı farklı yolu vardır: Diyelim ki, sıfır arkadaşı olabilir, bu durumda beş davetli ona tamamen yabancıdır. Ya da bir arkadaşı olabilir, bu durumda dört yabancı vardır. Bu çizelge, partiye katılan altı kişinin hostesle bağlantı kurmasının çeşitli yollarını gösterir.

Tablo, bir parti hostesinin beş konuğuyla olan farklı ilişkilerini göstermektedir.

Hostes (A kişisi) en az üç kişiyle arkadaştır ya da en az üç kişi onu tanımıyor. Bir grafikte bu, her zaman aynı renkteki en az üç kenarı olduğu gerçeğiyle görülebilir. Somut bir örnek kullanarak, tabloda gösterilen konfigürasyonlardan birinde hostesin üç kırmızı kenarı olduğunu, yani diğer üç misafiri tanıdığını varsayabiliriz. Şimdi kalan bağlantıları, 32.768 olası renklendirme takımyıldızı arasında kırmızı bir üçgenden kaçınılacak şekilde renklendirmeyi deneyebilirsiniz.

Altı nokta ve üç kırmızı çizgi.
Spektrum der Wissenschaft/Manon Bischoff

Bu yüzden hostesi tanıyan herhangi iki kişinin birbirini tanımadığından emin olmalısınız – aralarında mavi bir bağlantı olmalıdır. Ancak tüm bu kenarları mavi ile işaretlerseniz, mavi bir üçgen elde edersiniz! Yani, tüm düğümlerin bağlı olması gerekiyorsa, altı noktalı bir grafikte tek renkli bir üçgenden kaçınmanın bir yolu yoktur. Ve böyle bir üçgeni, tüm noktaların bağlı olduğu daha büyük herhangi bir grafikte bulabilirsiniz. Bu, beşten fazla misafir davet ettiğiniz anda, her zaman birbirini tanıyan veya tanımayan üç kişilik bir grup, tanıdık veya tamamen yabancı olan üç kişilik bir grup vardır.

Altı nokta, üç kırmızı çizgi ve üç mavi çizgi.
Spektrum der Wissenschaft/Manon Bischoff

Elbette matematikçiler tek bir sonuçla yetinmezler. Bunun yerine bir sorunu genelleştirmeye çalışırlar. Ramsey sayıları için genel bir durum elde etmek için, “Asgari düğüm sayısı nedir?” Diye sorarlardı. R her zaman bir kırmızı bulması gerekir m-klik veya mavi n-klik. Bir n-klik bir grup anlamına gelir n hepsi birbirine bağlı noktalar. elde edilen sayı R(m,n) Ramsey sayısı olarak adlandırılır. Şaşırtıcı bir şekilde, çok az sayıda Ramsey numarası bilinmektedir. Biz sadece bunu kanıtladık R(3,3) = 6. Şu da gösterilebilir: R(4,4) = 18. Bu, bir partiye 18 misafir davet ederseniz, her zaman birbirini tanıyan veya tanımayan dört kişilik bir grup olacağı anlamına gelir.

Ne kadar büyük olduğu onlarca yıldır belirsizdi. R(5,5), ancak. Diğer bir deyişle, her zaman tüm tanıdıklardan veya yabancılardan oluşan beş kişilik bir grup olması için davet etmeniz gereken en az misafir sayısı nedir? Uzmanlar sonucu daraltmayı başardılar: artık biliyoruz ki R(5,5) alt uçta 43 düğüme eşit veya daha küçük ve 48’e eşit veya daha küçük bir aralığa giriyor üst sınırdaki düğümler. Aynı renkten beşli bir grup içermeyen bir grafik olup olmadığını görmek için 43 düğümlü grafiklerin tüm olası renklerini gözden geçirmek için bir bilgisayar kullanabiliriz gibi görünebilir. Ama aslında, bu görev mevcut tüm bilgi işlem gücünü aşıyor!

Hepsi birbirine bağlı 43 düğümlü bir grafiğin 903 kenarı vardır. Bunlar kırmızı (arkadaşlar) veya mavi (bilinmeyen) olabilir. bu 2903 kabaca 10 olan olasılıklar272 yuvarlandığında. Bu 1 ve ardından 272 sıfır, ki bu da hayal edilemeyecek kadar büyük. Ne kadar büyük olduğunu anlamak için şu şekilde düşünülebilir: Şu anda evrenimizin yaklaşık 10 parçadan oluştuğu varsayılmaktadır.82 atomlar.

Diyelim ki bu atomların her biri saniyede çok sayıda hesaplama yapabilen bir hesap makinesiydi. şu anda en güçlü süper bilgisayar olarak: bir kentilyon (1018) saniyedeki hesaplama adımları. Her atomun bir saniyede beş kişilik bir grup için kentilyonlarca grafik arayabileceğini ve parçacıkların 13.8 milyar yıl önce, büyük patlamadan hemen sonra bunu yapmaya başladığını varsayalım. O zaman 13.8 x 10 olurdu9 x 365,25 x 24 x 3,600 ≈ 4,35 x 1017 şimdiye kadar bu görev için saniye. Yani evrendeki tüm atomlar yaklaşık 4,35 x 10’u incelerdi.117 bugüne kadarki grafikler—işlenecek kalanın yalnızca küçük bir kısmı.

Bu nedenle, matematikçiler soruna daha akıllı bir çözüm arıyorlar. Ancak şu ana kadar hiçbirini bulamadılar.

Bu makale ilk olarak Spektrum der Wissenschaft ve izin alınarak çoğaltılmıştır.



Kaynak : https://www.scientificamerican.com/article/ramsey-theory-extracts-order-from-chaos-when-sorting-through-confusing-arrangements-of-numbers/

Yorum yapın

SMM Panel PDF Kitap indir