RASTGELE AĞLAR SABİT BİR YOĞUNLUKTA BOYANABİLİR OLMAKTAN ÇIKIYOR
Bir graf alın — bağlantılarla birleştirilmiş noktalar — ve bir kutu renk. q renkle düzgün boyama (proper colouring), her noktaya q renkten birini verir; öyle ki bağlı iki nokta asla aynı rengi paylaşmaz. Az bağlantıyla bu kolaydır. Çok bağlantıyla imkânsız hâle gelir.
Şimdi grafı rastgele kuralım: n nokta; her nokta çifti küçük bir olasılıkla ve diğerlerinden bağımsız olarak bağlanıyor, böylece bir noktanın ortalama d komşusu oluyor. d büyüdükçe rastgele graf, “q renkle hemen hemen kesin olarak boyanabilir” durumundan “hemen hemen kesin olarak boyanamaz” durumuna geçer. Geçiş tam olarak nerede olur? Üçten başlayarak sabit herhangi bir q renk sayısı için bu soru, Cambridge Üniversitesi’nden Gaia Carenini’nin yeni bir makalesinin konusu.
Salınabilecek bir geçiş
Kaynakçada yer alan 1999 tarihli bir makalede Achlioptas ve Friedgut, geçişin keskin olduğunu kanıtladı: her n boyutu için öyle bir kritik ortalama derece d_q(n) vardır ki bunun biraz altında graf hemen hemen kesin olarak boyanabilir, biraz üstünde ise hemen hemen kesin olarak boyanamaz. Geçişin gerçekleştiği pencere daralarak yok olur.
Ama bu bir açık kapı bırakıyordu. Graflar büyüdükçe kritik değerin kendisinin salınmasını hiçbir şey engellemiyordu — bir boyuttaki graflar için bir yerde, daha büyükler için biraz başka bir yerde durup hiç yerleşmemesini. Achlioptas–Friedgut yakınsama sanısı bunun olmadığını söyler: her q için tek bir d_q sabiti vardır; bunun altında rastgele graflar boyanabilir, üstünde boyanamaz.
Fizikçilerin öngördüğü
İstatistiksel fiziğin, olup bitene dair bir tablosu vardı. Bağlantılar eklendikçe geçerli boyamalar kümeler (clusters) hâlinde toplanır: bir küme içindeki boyamalar birbirine benzer, iki küme ise pek çok noktada birbirinden ayrılır. Ardından, yoğuşma (condensation) denen bir aşamada, bir avuç büyük küme tüm boyamaların hatırı sayılır bir payını barındırır — ve ancak daha sonra geriye hiç boyama kalmaz. Bu düzen, sayma argümanlarının eşiğin yakınında neden zorlandığını açıklar.
Çok sayıda renk için önceki çalışmalar eşiği zaten dar bir aralığa sıkıştırmıştı: eşik yaklaşık 2q log q − log q − 2 log 2 ile 2q log q − log q − 1 arasında yer alır; q büyüdükçe aradaki boşluğun genişliği 2 log 2 − 1 olur. Ama “dar”, “sabit” demek değildir ve üç gibi küçük renk sayıları için soru açık kalmıştı.
Önce ele alınan ikiz bir problem
Boyamanın bir ikizi var: sağlanabilirlik (satisfiability), yani rastgele mantıksal kısıtlardan oluşan bir listenin tamamı sağlanacak biçimde değişkenlere doğru ya da yanlış değerler seçme problemi. Orada da keskin bir eşiğin var olduğu biliniyordu, ama yerleştiğine dair bir kanıt yoktu. Makalede atıf yapılan 2026 tarihli bir raporda Carenini, üçten başlayarak her kısıt uzunluğu için eşiğin yerleştiğine dair bir kanıt duyurdu; bunu, geçiş penceresinin çok dar olduğunu göstererek yaptı. Yeni makale bu argümanı boyamaya uyarlıyor.
Birlikte donmuş çiftler
Kanıt bir indirgemeler zinciri üzerinden ilerliyor. Rastgele bağlantılar birer birer eklenirken, H grafın boyanabilir olmaktan çıktığı an olsun. H bir rastgele graftan diğerine az değişiyorsa — yaklaşık n/(log n)² bağlantılık bir pencere içinde — eşik yerleşmek zorundadır. Klasik bir eşitsizlik bunu son boyanabilir graf hakkında bir soruya dönüştürür: bu graf, ortalamada kaç yeni rastgele bağlantıya dayanır?
İşte kilit kavram: donmuş çiftler. İki nokta, her geçerli boyama onlara aynı rengi verdiğinde donmuş bir çift oluşturur. Yeni bir bağlantı, tam olarak böyle bir çifti birleştirdiğinde ölümcüldür. Tek tek noktalar belirli bir renge donamaz, çünkü renklerin yerlerini değiştirmek her zaman başka bir geçerli boyama verir; zorunlu hâle gelen, iki nokta arasındaki bir ilişkidir. Carenini, bir bağlantıyı ya da bütün bir noktayı silip yeniden ortaya çıkan seçeneklere bakarak bu donmuş sınıfların bağlantılar eklendikçe nasıl büyüdüğünü izliyor. Kestirimler, son boyanabilir grafın uzun süre dayanamayacağını gösteriyor; bu da pencereyi sanıyı kanıtlamaya yetecek kadar daraltıyor.
Bilinmeyen ne kalıyor
Teorem, d_q eşiğinin her q ≥ 3 için var olduğunu söylüyor. Eşiğin nerede olduğunu söylemiyor: makale, üç renk için bile bir değer vermiyor. Makale tek yazarlı bir ön baskı ve hakem değerlendirmesinden geçmedi. Makale, matematiksel argümanlarının hiçbirinin büyük bir dil modeli tarafından üretilmediğini belirten kısa bir açıklamayla bitiyor.
