İki genç matematikçi, Kahn-Kalai varsayımlarının tam bir kanıtıyla meslektaşlarını şaşırttı- rastgele kümeler ve grafiklerin yapısının nasıl ortaya çıktığına dair kapsamlı bir açıklama.
Rastgele bir grafik bir üçgenle (sağda), bir Hamiltonian döngüsüyle (ortada) veya başka bir ilgi çekici özelliği ile sonuçlanacak mı?
Matematikçiler Jeff Kahn ve Gil Kalai, 2006 yılında “beklenti eşiği” varsayımlarını ilk kez ortaya attıklarında, buna kendileri de inanamadılar. Rastgele grafikler olarak adlandırılan matematiksel nesneler hakkında yaygın olan iddiaları, gerçek olamayacak kadar güçlü, her şeyi kapsayan ve çok cesur görünüyordu. Matematiksel gerçeğin bir yansımasından çok arzuladıkları düşünce gibi geldi. Öyle olsa bile, hiç kimse bunun yanlış olduğunu kanıtlayamadı ve hızla alandaki en önemli açık sorunlardan biri haline geldi.
Günümüzde, 15 yıldan uzun bir süre sonra, Stanford Üniversitesi’ndeki bir çift genç matematikçi, Kahn ve Kalai’nin neredeyse imkânsız olduğunu düşündükleri şeyi yaptılar: Jinyoung Park ve Huy Tuan Pham, birkaç hafta önce internette yayınladıkları şaşırtıcı derecede kısa bir özette, varsayımın tam bir kanıtını sundular.
Kalai, “Şaşırtıcı derecede basit ve dahiyane. Çarpıcı. Bu harika” dedi.
Sonuç, her birinin kendi başına kanıtlaması çok zor olan yüzlerce spesifik ifadeyi otomatik olarak kanıtlıyor- ve rastgele grafikler ve matematiksel kümeleri daha geniş bir şekilde anlamamız için daha da derin sonuçlara sahiptir..
Stanford’da matematikçi ve Pham’ın doktora danışmanı olan Jacob Fox, “Onların kanıtlarına sihirli diyebilirim. Bu, alanın ileriye gitmesinin önemli bir parçası olacak” dedi.
Grafiğin Dondurulması
Kahn-Kalai varsayımı çok kapsamlıdır- kümelerin ve öğelerin soyut dilinde yazılmıştır- ancak basit bir durum düşünülerek anlaşılabilecektir. İlk önce, bir grafik hayal edin: çizgiler veya kenarlarla birbirine bağlanan bir dizi nokta veya köşe. Rastgele bir grafik oluşturmak için, %1 veya %30 veya sıfır ile 100 arasında herhangi bir yüzdeyle tura gelen bir hileli para alın ve belirli bir köşe çifti için bir kez havaya atın. Madeni para tura gelirse, bu köşeleri bir kenarla birleştirin; madeni para yazı gelirse, bir şey yapmayın. Her olası köşe çifti için bu işlemi tekrarlayın.
Stanford Üniversitesi’nde matematikçi olan Jinyoung Park, “bu varsayımın güzelliğini ve gücünü hissedebiliyordum. Ama bunu kanıtlayacağımı hiç düşünmemiştim” dedi. Rod Searcey…
Matematikçiler, böyle bir grafiğin ne zaman ilginç bir yapıya sahip olacağını bilmek isterler. Belki bir üçgen içerecektir. Ya da belki bir Hamiltonian döngüsü, her tepe noktasından tam olarak bir kez geçen bir kenarlar zincirine sahip olacaktır. “Artan” olduğu sürece, özellikli bir grafiğe daha fazla kenar eklemek özelliğini yok etmeyecekse, herhangi bir özellik hakkında düşünmek mümkündür.
Madeni paranın tura gelme olasılığı düşükse, kenarlar nadir olacaktır ve Hamiltonian döngüleri gibi özelliklerin ortaya çıkması olası değildir. Ama olasılığı tersine çevirirseniz, garip bir şey olur. Her özelliğin eşik adı verilen bir değeri vardır: genellikle yapının çok aniden ortaya çıktığı olasılıktır.
Sıcaklık sıfır santigrat derecenin altına düştüğünde buz kristallerinin oluşması gibi, grafiğe daha fazla kenar eklendiğinde belirli bir özelliğin ortaya çıkması aniden son derece olası hale gelir. Örneğin, log(N)/N’den daha düşük bir olasılık ile N köşelerinin rastgele bir grafiğine kenarlar eklendiğinde, grafiğin bir Hamiltonian döngüsü içermesi olası değildir. Ancak bu olasılık log(N)/N’den sadece bir saç teli kadar daha büyük ayarlandığında, Hamiltonian döngüsü son derece olası hale gelir.
Matematikçiler, ilgilenilen çeşitli özellikler için bu tür eşikler belirlemek isterler. Fox, “Eşikler, belki de anlamaya çalışacağınız en temel şeydir. Rastgele bir nesneye bakıyorum; ilgilendiğim özelliği var mı?” dedi. Yine de Hamiltonian döngüleri ve diğer bazı özel yapılar için eşik hesaplanmış olsa da, çoğu durumda kesin bir eşik, hatta bir tanesinin iyi bir tahminini bile belirlemek çok zordur.
Bu nedenle matematikçiler genellikle, eşik için olası minimum değere veya alt sınırı sağlayan daha kolay bir hesaplamaya güvenirler. Bu “beklenti eşiği”, esas olarak ağırlıklı bir ortalama alınarak hesaplanır. California Institute of Technology’de matematikçi olan David Conlon, “Bu beklenti eşiğinin güzel yanı, hesaplanmasının çok kolay olmasıdır. Genel olarak konuşursak, neredeyse her şey için bu beklenti eşiğini iki kenar/çizgi gibi hesaplayabilirsiniz” dedi.
Ancak ortalamalar yanıltıcı olabilir. Örneğin Hamiltonian döngüleri için, beklenti eşiği 1/N’dir ve bu, log(N)/N’nin gerçek değerinden bir log(N) çarpımı kadar düşüktür.
Gil Kalai, Kudüs İbrani Üniversitesi’nden. Quanta Magazine için Daniel Vaaknin
2006’da Kahn ve Kalai bunun aslında en kötü senaryo olduğunu öne sürdüler. Onların isimsiz varsayımı, beklenti eşiği ile gerçek eşik arasındaki boşluğun asla logaritmik bir faktörden daha büyük olmayacağını belirtir. Conlon’a göre varsayım, “temelde rastgele grafiklerde merkezi sorunun ne olduğunu alır ve bunun için genel bir cevap verir.”
Ama bu sadece basit bir durum. Varsayım, rastgele grafiklerden çok daha fazlasıyla ilgilidir. Doğruysa, rastgele sayı dizileri, hipergraf adı verilen grafiklerin genelleştirilmesi ve hatta daha geniş sistem türleri için geçerlidir. Bunun nedeni Kahn ve Kalai’nin açıklamalarını soyut kümeler cinsinden yazmalarıdır. Rastgele grafikler belirli bir durumu oluşturur- bir rastgele grafik, tüm olası kenarların rastgele bir alt kümesi olarak düşünülebilir- ancak varsayımın kapsamına giren birçok başka nesne vardır. Conlon, “Garip bir şekilde, grafiklerle uğraşırken bunu bu bağlamda kanıtlamak çok zor olurdu. Ama bir şekilde, bu soyut ortama atlamak, o şeyin merkezini ortaya çıkarıyor” dedi.
Bu ifadenin inanılmaz görünmesini sağlayan bu genellemeydi. San Diego’daki California Üniversitesi’nde teorik bilgisayar bilimci olan Shachar Lovett, “Bu çok cesur bir varsayımdı” dedi. Birincisi, farklı özellikler için eşikleri hesaplamaya çalışmak, birleştirici büyük bir çabayı anında düzene sokacaktır. Carnegie Mellon Üniversitesi’nde matematikçi olan Alan Frieze, “Görünüşte kanıtların çok uzun ve karmaşık olması gereken sorular, birdenbire ortadan kayboluyor. Kanıtlar, bu [varsayımın] sadece önemsiz uygulamaları haline geldi” dedi.
Görünüşte alakasız birçok problemin bu kadar geniş bir varsayımla çözülebileceği anlaşılınca birçok matematikçi kendini gergin hissetti denilebilir. Conlon, “Dürüst olmak gerekirse tamamen çılgınca görünüyordu” dedi. Kahn ve Kalai, varsayımlarını geliştirdikten sonra bunu kanıtlamaya çalışmadılar; bir karşı örnek bulmaya çalıştılar. Keşfedebilecekleri o kadar çok düzenleme vardı ki, sonunda bir tanesine rastlamak zorunda kalacaklarını düşündüler.
Ancak ortaya çıktığı gibi, Kalai, “hikâyenin beklediklerinden çok farklı bir şekilde geliştiğini” söyledi.
Ayçiçeği Yolu
Sonunda Kahn-Kalai varsayımının yeni kanıtına yol açacak yöntemler, görünüşte alakasız bir promlemdeki buluşla başladı. Birçok yönden hikaye, 1960 yılında matematikçiler Paul Erdős ve Richard Rado tarafından ortaya atılan, bir soru olan ayçiçeği varsayımıyla başlar. Ayçiçeği varsayımı, küme koleksiyonlarının bir ayçiçeğinin taç yapraklarına benzeyen şekillerde oluşturulup oluşturulamayacağını değerlendirir.
2019’da Lovett, ayçiçeği sorununun tam çözümüne çok yaklaşan bir ekibin parçasıydı. O zamanlar, çalışma, olasılık değerlendirmelerini içeren Kahn-Kalai varsayımından tamamen ayrı görünüyordu. Kalai, “Tahminimizle herhangi bir bağlantı görmedim” dedi. “Bu [diğer] sorulardan haberimiz yoktu” diyen Lovett da öyle değildi. Ayçiçeklerini önemsiyorduk.”
Ancak Kahn, Park (o zamanlar Kahn’ın doktora öğrencisiydi) ve meslektaşları, birkaç ay sonra Kahn-Kalai varsayımının daha rahat bir versiyonunu kanıtlamak için yola çıktıklarında ikisini birbirine bağladılar. (Onların ispatı geçen yıl Annals of Mathematics’te yayınlandı.) Fransız matematikçi Michel Talagrand tarafından formüle edilen bu daha zayıf versiyon, Kahn-Kalai beklenti eşiğini “kesirli” bir beklenti eşiğiyle değiştirdi- esasen ağırlıklı bir ortalama almanın farklı bir yolu. Lovett, revize edilmiş tanımın “size şeylerle çalışmak için daha fazla hareket alanı sağlıyor” dedi.
Kahn ve Park’ın ekibi, 2019 ayçiçeği sonucundan teknikleri ihraç edebileceklerini, ince ayar yapabileceklerini ve Talagrand varsayımına uygulayabileceklerini fark etti. Kahn, “Bizi başlatan kesinlikle bu oldu” dedi.
Matematikçiler probleme yinelemeli bir yaklaşım getirdi. Rastgele bir küme- diyelim ki rastgele bir grafik- seçerlerse, bunun Hamiltonian döngüsü gibi bir yapı içereceğini göstermek için yola çıktılar. Ancak bu rastgele kümeyi bir kerede seçmek yerine, Lovett ve meslektaşlarının ayçiçeği varsayımına yaklaşma biçimine benzer bir süreçle onu, parçalar halinde seçtiler. Park, “Bir çeşit rastgele süreci yinelemeli olarak gerçekleştiriyoruz. Tüm bir Hamiltonian döngüsü içerene kadar, bazı kenarları adım adım seçiyoruz”dedi.
Bunu yapmak için ekip, yayılma adı verilen bir rastgelelik kavramına yöneldi. Hamiltonian çevrimleri iyi bir şekilde “yayılırsa”, bu, çok fazla döngünün aynı kenarı veya kenarların alt kümesini içermediği anlamına gelir. Pham, “Her nasılsa, kümeler koleksiyonu uzayda dağılmış durumda, çok kümelenmiş veya herhangi bir parça üzerinde yoğunlaşmış değil.” dedi. “Döngüler bu şekilde iyi dağıtılırsa, rastgele parça parça içerme sürecinin- birçok Hamiltonian döngüsü için başarısız olsa bile- en az birini yakalamayı başaracağını garanti eder.
Yaklaşım ancak kritik bir denklik sebebiyle mümkün oldu: Yayılım, doğrudan kesirli beklenti eşiğiyle ilgili bir şekilde ölçülebilir. Bu nedenle, matematikçiler Talagrand varsayımını yayılma açısından yeniden yazabildi.
Şaşırtıcı bir şekilde, bu daha zayıf varsayımın kanıtı, eşiklerle ilgili bir dizi sorunu çözmek için yeterliydi. Kahn, “Tam varsayım için bildiğimiz her sonuç, aynı zamanda zayıf varsayımın bir sonucudur” dedi. Aslında, ona, Kalai ve diğerlerine göre bu, iki varsayımın aşağı yukarı aynı olabileceğini- kesirli ve orijinal beklenti eşiklerinin değerlerinin temelde eşdeğer olduğunu ileri sürdü. Birisi bu denkliği kanıtlayabilirse, Kahn-Kalai varsayımını kanıtlamış olur. Kahn, “Her zaman varsayımımızı kanıtlamanın tek yolunun bunu kanıtlamak olduğunu düşündüm” dedi.
Ama bu olmadı. Diğer matematikçiler Kahn-Kalai varsayımının tam bir kanıtı için bu yol haritasını izlemeye çalışırken, Park ve Pham tamamen yeni bir yaklaşım buldu. Conlon, “Jinyoung ve Huy, bu inanılmaz derecede doğrudan, inanılmaz kısa argümanı buldular ve tüm bunları doğrudan doğruya getirdiler. Bu olağanüstü. Bunu hiç beklemiyordum.” dedi.
Kahn kabul etti. “Bu, matematikte olan güzel şeylerden biri. İnsanların umutsuz olduğunu düşündükleri şeyler, yalnızca umutsuz değil, aynı zamanda zor da değildir” dedi.
Sürpriz Bir Yaklaşım
İlk başta ne Park ne de Pham’ın orijinal varsayımı ele alma niyeti yoktu. Bir yüksek lisans öğrencisi olarak sorunu ilk öğrendiğinden beri Park, “Bu varsayımın güzelliğini ve gücünü hissedebiliyordum” “Ama bunu kanıtlayacağımı hiç düşünmemiştim” dedi.
Pham, “Aklımızda hiç yoktu,” diye ekledi.
Pham’ın söylemine göre, Pham ve Park, bunun yerine, Talagrand’ın “bir ilham ile vurulduklarında” ortaya koyduğu başka bir varsayım üzerinde çalışıyorlardı. “Burada sahip olduğumuz resim, sahip olduğumuz fikirler, bir şekilde göründüğünden daha güçlüymüş gibi göründüğünü” fark ettiler. Bu fikirlerin, onları Kahn-Kalai sorununun bir kanıtı boyunca sonuna kadar götürmeye yetecek kadar güçlü olabileceğini düşündüler.
Mart ayında tek bir uykusuz gece boyunca, ispatın nasıl işe yarayacağını anladılar.
Kesirli beklenti eşiğinden farklı olarak, normal beklenti eşiğinin yayılma ile hiçbir ilişkisi yoktur. Kahn, Yayılma “size bir başlangıç noktası verir. Ve orijinal, kesirli olmayan varsayıma giderseniz, bu başlangıç noktası ortadan kaybolur. Yani çok zor görünüyordu” dedi.
Pham “Ee ne yaparsın? Bu durumda, bakış açımızı değiştiriyoruz” dedi.
Özellikle, problemi örtü adı verilen matematiksel bir nesne açısından düşündüler. Örtü, belirli bir özelliğe sahip her nesnenin bu kümelerden birini içerdiği bir kümeler topluluğudur. Örneğin, tüm Hamiltonian döngülerinin olası bir örtüsü, tüm kenarların toplamasıdır. Her Hamiltonian çevrimi bu kenarlardan birini içerecektir.
Park ve Pham, Kahn-Kalai varsayımını, örtüleri kullanmalarına izin verecek şekilde yeniden yazdı. Orijinal varsayım, rastgele bir grafiğin veya kümenin bazı özellikler içerdiğini garanti etmek için ağırlıklı bir madeni paranın tura gelme olasılığının ne olması gerektiğine dair kısıtlamalar getirir. Özellikle, olasılığın en azından özellik için bir logaritmik faktörle çarpılan beklenti eşiği olması gerektiğini söylüyor. Park ve Pham bunu tersine çevirdi: Böyle bir özelliğin ortaya çıkması muhtemel değilse, o zaman hileli madeni paraya atanan olasılık, bir logaritmik faktörle çarpılan beklenti eşiğinden daha düşüktür.
Örtülerin devreye girdiği yer burasıdır: Yapıların bir alt kümesi için küçük bir örtü oluşturulabildiğinde (Hamiltonian döngülerinin bir koleksiyonu gibi), bu, alt kümenin beklenti eşiğine katkısının küçük olduğu anlamına gelir. (Beklenti eşiğinin, belirli bir türdeki tüm olası yapılar üzerinden bir tür ağırlıklı ortalama alınarak hesaplandığını unutmayın.) Dolayısıyla Park ve Pham’ın şimdi göstermesi gereken şey, eğer rastgele bir kümenin tek bir hedef yapı içermesi olası değilse, bu tür tüm hedef yapıları için küçük bir örtünün olması gerektiğiydi. Kanıtlarının büyük kısmı bu küçük örtüyü oluşturmaya adanmıştı.
Bunu, önceki sonuçlarda kullanılana benzer bir parça parça örnekleme süreci kullanarak ve aynı zamanda Fox’un “çok zekice sayma argümanı” dediği şeyi ortaya koyarak yaptılar. Mart ayında geçirdikleri uykusuz geceden bir hafta sonra, altı sayfalık zarif makalelerini çevrimiçi olarak yayınladılar.
Lovett, “Kanıtları çok basit. Geliştirdiğimiz temel fikri ve bu diğer makalelerden [fikirleri] alıyorlar ve ona bir bükülme ekliyorlar. Ve bu yeni bükülme ile her şey bir şekilde çok, çok daha kolay hale geliyor” dedi.
Frieze kabul etti. “Bunu açıklayamam, ama şaşırtıcı bir şekilde doğru” dedi.
Kesirli sonuç gibi, şimdi doğru olduğu kanıtlanmış olan Kahn-Kalai varsayımı da otomatik olarak ilgili varsayımların bolluğunu ima eder. Ancak bundan daha fazlası, Princeton Üniversitesi’nde matematikçi olan Noga Alon, “Bu, muhtemelen yeni şeylere yol açacak güçlü bir ispat tekniği. Bunu doğru şekilde yapmaları gerekiyordu” dedi.
Park ve Pham artık yöntemlerini başka sorunlara da uygulamaya başladılar. Özellikle, beklenti eşiği ile gerçek eşik arasındaki boşluğu daha kesin bir şekilde anlamakla ilgileniyorlar. Kahn-Kalai varsayımını kanıtlayarak, bu boşluğun en fazla logaritmik bir faktör olduğunu gösterdiler- ancak bazen boşluk daha küçüktür, hatta hiç yoktur. Henüz, bu senaryoların her birinin ne zaman doğru olabileceğini sınıflandırmak için daha geniş bir mekanizma yok; matematikçiler duruma göre çözmek zorundadır. Pham, “Sahip olduğumuz bu verimli teknikle, bu eşikleri belirlemede umarız çok daha kesin olabileceğimizi düşünüyoruz” dedi.
Ve kanıtlarının başka sonuçları da olabilir. Park, “Kahn-Kalai varsayımı hikâyenin sonu değil” dedi.
Yazar: Hüseyin Türker
Editör: Damla Gözük
Kaynaklar:
Konuyla ilgili öncül bir blog 21 Ekim=2019’da yayınlanmış:
Yoruma kapalı.