21 yıllık graf sandviçi sanısı kanıtlandı: rastgele ağlara köprü

Quanta Magazine'in 18 Eylül'de duyurduğu üzere, o öneri artık bir teorem. Warwick Üniversitesi'nden Richard Montgomery ile çalışma arkadaşları Natalie Behague ve Daniel Il'kovič, "sandviç sanısı" olarak bilinen problemi tam olarak çözen bir kanıt yazdı.

Graf nedir, iki rastgele graf neden farklıdır

Graf (Türkçede çizge), noktalar ve onları birleştiren çizgilerden ibaret bir soyutlamadır. Noktalara köşe, çizgilere kenar denir; bir köşenin kaç kenarı varsa ona o köşenin derecesi denir. İnsanlar ve arkadaşlıkları, sunucular ve kablolar, hücreler ve temas noktaları — hepsi graf olarak yazılabilir.

1950'lerin sonunda Edgar Gilbert ile ondan bağımsız olarak Paul Erdős ve Alfréd Rényi, telefon ağları gibi yapıları incelemek için binom rastgele graf modelini kurdu: her köşe çifti için belirli bir p olasılığıyla bağımsız bir para atılır, yazı gelirse kenar çizilir. Modelin güzelliği bağımsızlıkta. Bir kenarın varlığı diğerleri hakkında hiçbir şey söylemediği için olasılık hesapları rahatça yürür.

Rastgele d-düzenli graf ise farklı bir tariftir: tüm köşelerin derecesi tam olarak d olan graflar arasından biri rastgele seçilir. Burada bağımsızlık yoktur. Bir kenarı çizdiğiniz anda iki köşenin kalan kotası azalır, bu da bütün ağın olasılık dağılımını sarsar. Domino taşları gibi: birine dokununca hepsi biraz kayar.

Buna karşılık düzenli graflar gerçek dünyaya daha çok benziyor. Bir veri merkezinde her anahtarın aynı sayıda portu vardır; bir yönlendirici sınırsız kablo kabul etmez. Nitekim 2012'de USENIX NSDI konferansında sunulan Jellyfish çalışmasında Ankit Singla, Chi-Yao Hong, Lucian Popa ve P. Brighten Godfrey, veri merkezi kablolamasını doğrudan rastgele düzenli graf olarak kurmayı önermiş, aynı donanımla birkaç bin düğüm ölçeğinde klasik "fat-tree" tasarımına göre yüzde 25'e varan daha fazla sunucuyu tam kapasitede besleyebildiklerini bildirmişti.

"Sandviç" tam olarak neyi kastediyor

Jeong Han Kim (o sırada Microsoft Research'te) ve Van Ha Vu (o sırada Kaliforniya Üniversitesi San Diego'da), 2004'te Advances in Mathematics dergisinde yayımladıkları çalışmada şunu öne sürdü: rastgele bir d-düzenli graf, kenar olasılıkları d/n'ye çok yakın iki binom grafın arasına yerleştirilebilir. Alttaki seyrek binom graf tamamen düzenli grafın içinde kalır, düzenli graf da üstteki biraz daha yoğun binom grafın içinde kalır.

Buradaki incelik, üç grafın ayrı ayrı çizilip sonra karşılaştırılması değil. Üçü aynı anda, birbirini gözeterek üretilmeli — matematikçilerin eşleme (coupling) dediği şey budur. Sonuç, iç içe geçmiş üç matruşka gibidir: en dıştaki kutuyu açınca ortadaki, onu açınca en içteki çıkar ve hiçbiri diğerine takılmaz. Üstelik bunun yüksek olasılıkla, yani köşe sayısı büyüdükçe neredeyse kesinlikle olması gerekir.

Böyle bir iç içe geçme kurulduğunda kazanç şudur: "daha çok kenar eklendikçe bozulmayan" türden bir özellik — sözgelimi ağda bütün köşelerden bir kez geçen kapalı bir tur bulunması — alttaki binom grafta kanıtlanırsa, düzenli grafa kendiliğinden taşınır. Quanta'nın aktardığına göre binom graflarda bu tür turların hangi koşulda ortaya çıktığı 1970'lerde çözülmüş, aynı sonucun düzenli graflardaki karşılığı ise ancak yirmi yıl kadar sonra gelebilmişti.

Behague, bağlantıyı Quanta'ya "neredeyse doğru olamayacak kadar iyi" diye tarif etti.

Yirmi bir yıl süren yaklaşma

Sanı ortaya atıldıktan sonra uzun süre kısmi sonuçlarla ilerlendi. En önemli adım, Pu Gao (Waterloo Üniversitesi), Mikhail Isaev ve Brendan McKay'den geldi: 2019'da arXiv'e konan ve 2020'de SODA konferansında sunulan çalışmalarında bir eşleme yordamı tanımladılar, ardından sanının d derecesi log n'in dördüncü kuvvetinden çok büyük olduğunda doğru olduğunu gösterdiler. Yeni kanıt da tam olarak bu yordamı kullanıyor; farkı, onu çok daha seyrek ağlarda çözümleyebilmesi.

Kanıtın fikri: dilim değil, rendelenmiş peynir

Kanıtın kalbinde sabırlı bir inşa var. Üç graf da boş köşe kümelerinden başlıyor ve kenarlar teker teker, ağırlıklı paralarla ekleniyor. Binom grafa bir kenar düştüğünde aynı kenarın düzenli grafa da düşüp düşmeyeceğine ikinci bir para karar veriyor; bu ikinci para, kalan kenarların hâlâ herkesin derecesini tam d yapacak şekilde tamamlanabilmesini gözetiyor. Üst katman için aynı iş tersinden, dolu graflardan kenar silerek yürütülüyor.

Quanta'nın benzetmesiyle söylersek, sandviç tek bir peynir dilimi koyarak değil, rendelenmiş peyniri serperek kuruluyor. Tel Aviv Üniversitesi'nden Michael Krivelevich, dergiye kanıtın zorluğunu anlatırken "her adım çok iyi bir teknik gerektiriyor" dedi ve tamamlanmış kanıtı görünce rahatladığını söyledi. Kudüs İbrani Üniversitesi'nden Gil Kalai ise sonucu, "araç çantamızı zenginleştiren" bir meta-teorem olarak niteledi: tek bir soruyu değil, bütün bir soru sınıfını aktarmayı sağlıyor.

Sonucun sınırı

Bu kanıt her rastgele düzenli grafı kapsamıyor. Kim ve Vu sanıyı en baştan bir eşiğin üstü için kurmuştu: köşe sayısı n büyürken derece d, log n'den daha hızlı büyümeli. Dolayısıyla derecesi sabit kalan ağlar — her köşesi tam üç bağlantılı graflar gibi — sandviçin dışında. Bu, kanıtın eksiği değil, problemin tanımlı olduğu aralık; ama "artık bütün düzenli graflar binom graflara indirgendi" demek yanlış olur.

İkinci sınır, aktarılan özelliklerin türü. Sandviç, yalnızca kenar eklendikçe korunan ya da kaybolan tek yönlü özellikleri rahatça taşır. "Tam olarak şu kadar üçgen içerir" gibi iki yönlü bir ifade, iki katman arasında sıkışıp kalır.

Üçüncüsü ve en somutu: çalışma şu an bir önbaskı. 53 sayfalık metin arXiv'de, aralık 2025'te güncellenmiş ikinci sürümüyle duruyor ve herhangi bir dergi künyesi taşımıyor; yani olağan hakem sürecini henüz tamamlamış değil. Alanın önde gelen isimlerinin kanıtı okuyup olumlu konuşması güçlü bir işaret, fakat hakemliğin yerini tutmuyor.

Sırada ne var

Ekibin açık bıraktığı soru, sandviçin katmanlarını çoğaltmak. Binom ve düzenli grafların art arda dizildiği çok katlı yapılar kurulabilirse, kısıtlı ve kısıtsız rastgeleliğin birbirine ne kadar yakın olduğu daha da netleşecek. Daha genel sorusu ise şu: dereceleri eşit olmayan ama yine de belirli bir dağılıma uymak zorunda olan ağlar — gerçek toplumsal ağların çoğu böyledir — aynı biçimde iki kolay modelin arasına sıkıştırılabilir mi? Bunun cevabı hâlâ yok.

Fotoğraf: Gaetano Cirianni, CC BY-SA 4.0, Wikimedia Commons