Matematikçiler Uzun Süredir Beklenen “Graf Sandviçi”ni Kurdu

2004 yılında iki matematikçi, güçlü bir “sandviç” türünün var olabileceğini öne sürmüştü. Yirmi yılı aşkın süredir çaba sarf eden alan araştırmacıları, bu iddianın tam ispatını uzun süre başaramadı; ancak 2025 yılında üç matematikçi, kendi disiplinlerinin tekniklerini en üst düzeye taşıyarak bu arayı kapattı ve kanıtı tamamladı.

Sözkonusu sandviç, noktaların (matematikte “köşeben” olarak adlandırılan) ve çizgilerin toplulukları olan graf teorisinde yer alıyor. Graf sosyal gruplardan internete, oradan beyindeki nöronlara kadar her şeyi temsil edebilir. Matematikçiler, matematikte ve bilişim biliminde yaygın ancak analizi zor bir graf türünün özelliklerini anlamayı hedefliyordu; bunu yaparken de söz konusu karmaşık grafiği, matematiksel açıdan sağlam iki basit graf arasına yerleştirmeyi planladı.

Sandviç İddiasının Gücü

Böyle bir sandviçin var olabileceğinin ispatlanması, araştırmacılara yalnızca ortadaki grafiğin ilgilendikleri tek özelliğe sahip olduğunu göstermezdi; aynı zamanda grafiğin çeşitli önemli özelliklerinin tümüne sahip olduğunu ortaya koyardı. Bunu başarırken de matematikçilerin sık çalıştığı iki oldukça farklı rastlantısallık sürecinin, hayal ettikerinden çok daha derin ve zarif bir biçimde birbirine bağlı olduğu kanıtlanırdı.

Bu kavram o kadar güzeldir. Bana en çok çeken şey aslında bunun güzelliğidir.

Pu Gao, Kanada’daki Waterloo Üniversitesi Matematikçi

Gao, bu sorun üzerinde çalışan matematikçilerden biri olarak iddianın güzellğine dikkat çekiyor. Son iki on yılda, “sandviç iddiası” adı verilen ve ilgilendiğiniz grafiğin yeterince büyük olması koşuluyla gerekli sandviçi her zaman kurabileceğinizi öne süren bu konuda ilerleme kaydedildi; ancak kimse onu tam olarak ispatlayamadı.

Rastlantısallık Graf Türleri

Olayın kökeni 1950’lerin sonuna, Amerikalı matematikçi Edgar Gilbert’in Bell Labs’ta telefon ağlarını çalıştığı döneme dayanıyor. Bu ağları daha iyi anlamak için, köşebenlerin rastlantısallıkla birbirine bağlandığı basit bir “rastlantısallık” graf modeli geliştirdi. Yaklaşık olarak aynı dönemde matematikçiler Paul Erdős ve Alfréd Rényi de benzer bir modelden bağımsız biçimde yararlandı.

Bu türden bir grafiği oluşturmak için önce bir köşeben kümesiyle başlarsınız. Sonra bu kümedeki herhangi iki köşebeni seçin ve (öğneli bile olabilir) bir para atın. Yazı düşerse aralarında bir çizgi çizin; aksi halde sonrakine geçin. Bu adımı graf içindeki her köşeben çifti için tekrarlayın.

Rastlantısallık binomial grafiği olarak bilinen bu graflar, ağları temsil etmek için kullanışlı —üstelik kusurlu da olsa— bir yol sundu. Görelatively kolay analiz edilebiliyor ve matematikçiler hakkında birçok ilginç şey ispatladı. Örneğin 1970’lere gelindiğinde, rastlantısallık binomial grafiğinin hangi koşullar altında Hamilton döngüsü içereceğini keşfettiler; Hamilton döngüsü, her köşebeni tam olarak bir kez ziyaret eden bir yoldur.

Ancak bu, rastlantısallık grafının tek türü değil. Matematikçiler, tüm köşebenlerin aynı sayıda çizgiye sahip olduğu rastlantısallık grafları konusunda da meraklıydı. “Düzenli graf” olarak adlandırılan bunlar, binomial graflardan daha iyi bir rastlantısallık yapısı anlayışı sağlıyor ve gerçek dünya ağlarını modellemede çoğu zaman çok daha doğru oluyor.

Ancak çizgileri daha kısıtlı ve birbirine bağımlı örüntüler oluşturduğu için analizi de çok daha zor. Binomial graflar için Hamilton döngüsü sorusunun yanıtlanması, düzenli graflar için aynı işin yapılabilmesine kadar ek 20 yıllık bir çaba gerektirdi.

Düzenli Grafiği Yaklaşık Olarak Kurmak

Peki ya rastlantısallık düzenli grafları, rastlantısallık binomial graflarla yaklaşık olarak temsil edebilseydik? Bu mümkünse, matematikçiler bir grafın kanıtlanması zor birçok özelliğini, eşleşen binomial grafından neredeyse ücretsiz biçimde alabilirdi.

2000’lerin başında, o sıralar Microsoft Research’de bulunan Jeong Han Kim ile Kaliforniya Üniversitesi San Diego Kampüsü’nde çalışan Van Ha Vu, bir grafiği sandviç haline getirerek bunu nasıl yapabileceklerini gösterdi.

Fikrin gevşek tanımı, hem binomial hem de düzenli bir grafiyi aynı anda inşa edecek tek bir tarif —bir rastlantısallık süreci— bulmaktı. Bu tarifiň yalnızca doğru türde grafları üretmesi değil, aynı zamanda bu grafların tam da gerekli biçimde birbirine oturması gerekiyordu. Bunu başarabilirseniz, görelatively kolay analiz edilen binomial graf hakkında sonuçlar ispatladığınızda, bu sonuçların düzenli graf için de geçerli olması gerekir.

Sandviç benzetmesinde, ekmek dilimlerinden birinin özellikleri hakkında kanıt yapmak ve bu sonuçların ortadaki peynir için de geçerli olacağını bilmek gibidir. Ancak graflar tam olarak nasıl birbirine oturmalıdır? Peyniri her ekmeğin üzerine ayrı ayrı yerleştirecek bir tarif bulmanız gerekir.

Öncelikle, size düzenli bir graf veren bir tarife ihtiyacınız var; bu graf içinde bir binomial graf içeriyor olmalı. Yani binomial grafiğin çizgileri, düzenli grafiği oluşturan çizgilerin bir altkümesi biçiminde olur. Bu binomial grafın, grafa çizgi eklendiğinde ortaya çıkması daha muhtemel herhangi bir özelliğe sahipse, düzenli grafiniz de aynı özelliğe sahip olacaktır. Bu, Kim ve Vu’nun sandviçinin alt yarısıdır.