AĞLAR İÇİN BİR SINIR, ARTIK HER BOYUT İÇİN KANITLANDI

Birkaç nokta alın ve bazı çiftlerini çizgilerle birleştirin. Matematikçiler buna çizge (graph) der: noktalar onun köşeleri, çizgiler kenarlarıdır; iki köşe arasındaki uzaklık da birinden ötekine yürümek için gereken en az kenar sayısıdır. Şimdi iki kural ekleyin. Her köşe çifti en fazla 2 uzaklıkta olmalı — doğrudan bağlı ya da ortak bir komşu üzerinden. Ve hiçbir kenar fazlalık olmamalı: herhangi birini silin, bir çift iki adımdan uzağa düşsün. Böyle bir çizgeye çap-2-kritik (diameter-2-critical) denir. Kaç kenarı olabilir?

Mantel’in tavanı ve daha cüretkâr bir tahmin

1907’de Mantel, n köşeli ve üçgensiz — üçü de birbirine bağlı üç köşe barındırmayan — bir çizgenin en fazla ⌊n²/4⌋ kenarı olduğunu kanıtladı: n’nin karesinin dörde bölümü, aşağı doğru tam sayıya yuvarlanmış. Bu tavana yalnızca tek bir çizge ulaşır: dengeli tam iki parçalı çizge (balanced complete bipartite graph); olabildiğince eşit büyüklükte iki grup, birinin her köşesi ötekinin her köşesine bağlı, grup içinde hiç kenar yok.

Üçgen oluşturmadan bir kenar daha alamayan her üçgensiz çizge çap-2-kritiktir. Tersi doğru değil: bazı çap-2-kritik çizgeler üçgen içerir.

v1v3v5 üçgenini içeren, 7 köşeli ve 9 kenarlı çap-2-kritik bir çizge. v1v3’ü silmek, v2 ile v3 arasındaki tek iki adımlık yolu yok eder; üçgenin dışındaki bir kenarı silmek, uçlarını iki adımlık bir yoldan yoksun bırakır. — Şekil 1, Das & Fox (2026), arXiv:2610.39032.

Tahmin şuydu: üçgenler hiçbir şey kazandırmaz; n köşeli çap-2-kritik bir çizgenin yine en fazla ⌊n²/4⌋ kenarı vardır ve bu sınıra yine yalnızca dengeli tam iki parçalı çizge ulaşır. Mantel teoremi özel bir durum olarak bundan çıkardı. Şekildeki 7 köşe için tavan 12 kenardır.

Bir 2’ler kulesi

Zoltán Füredi’nin aktardığına göre Erdős, sorunun Ore’un 1960’lardaki çalışmalarına dayandığını söylüyordu. Ján Plesník kenar sınırını 1975’te bir varsayım olarak ortaya koydu; Murty ve Simon bunu bağımsız olarak önerdi ve tek uç durumun dengeli tam iki parçalı çizge olduğunu ekledi — Murty–Simon varsayımı adı buradan geliyor. 1970’ler ve 1980’lerde c·n² biçimindeki sınırlar, c giderek 1/4’e yaklaşacak şekilde yavaş yavaş düştü.

1992’de Füredi varsayımı, Szemerédi’nin düzenlilik önsavından türetilen araçlar olan düzenlilik yöntemleriyle (regularity methods), yeterince büyük her n için kanıtladı. Bedeli başlangıç boyutuydu: n en az yüksekliği kabaca 10¹⁴ olan bir 2’ler kulesi kadar olmalıydı; yani yukarıdan aşağıya doğru hesaplanan 2 üzeri 2 üzeri 2… — her 2, üstündeki her şeyin kuvvetine yükseltilir —, yığında yaklaşık 10¹⁴ tane 2 bulunan bir sayı. Bu boyutun altında yalnızca özel çizge aileleri çözülmüştü.

Kenarlar ve eksik kenarlar

Stanford Üniversitesi Matematik Bölümü’nden Sanjana Das ve Jacob Fox’un yeni kanıtı, 3’ten başlayarak her n için geçerli. Bir maksimal eşleme (maximal matching) kullanıyor: hiçbir ikisi bir köşeyi paylaşmayan ve ikisi buluşmadan yeni bir kenar eklenemeyen bir kenar kümesi. n köşe üzerindeki bir eşleme en fazla ⌊n/2⌋ kenar içerir.

Temel önsav: çap-2-kritik bir çizgede, herhangi bir maksimal eşleme için, eşlemenin dışındaki kenarlar hiçbir zaman kenar-olmayanlardan (non-edges) — birbirine bağlı olmayan köşe çiftlerinden — daha çok değildir. Gerisi aritmetik. Kenar sayısının iki katı, en fazla çift sayısı artı eşlemenin büyüklüğü kadardır. 10 köşeyle: 45 çift artı en fazla 5 eşleme kenarı 50 eder, dolayısıyla en fazla 25 kenar. Her n için bu toplam tam olarak Mantel tavanının iki katına eşit.

Önsavın kendisi titiz bir muhasebe. Bir kenar-olmayan, uçlarını tek bir iki adımlık yol birleştiriyorsa kritiktir; Şekil 1’deki on iki kenar-olmayanın hepsinde olduğu gibi. Yazarlar her kritik kenar-olmayanı kendi yolunun iki kenarına iliştiriyor ve ortaya çıkan ağı bağlantılı parçalara bölüyor. Bir parça, kritik kenar-olmayanlarından en fazla bir fazla kenar içerir ve bu fazlalığı taşıyan her parçanın bedeli kritik olmayan bir kenar-olmayanla ödenmelidir. Yazarlar bunları bulmak için değiş tokuş çıkışlarını (switch exits) kullanıyor: parçanın bir kenarını ya da kritik kenar-olmayanını alın ve uçlarından birini, o ucun eşlemedeki eşiyle değiştirin. Kritik olmayan her kenar-olmayan en fazla iki kez talep edilir, fazlalıklı her parça en az iki talepte bulunur ve hesap kapanır.

Kim neyi buldu

Yazarlar kısa bir yapay zekâ beyanında “Bu kanıtı çoğunlukla yapay zekâ, özellikle 11 Ağustos 2026’da GPT-5.6 Sol buldu” diye yazıyor. Model ⌊n²/4⌋ sınırının tam bir kanıtını buldu; yazarlar bunu sadeleştirdi. Çift sayıda köşe için model, tek uç durumun dengeli tam iki parçalı çizge olduğunu da kanıtladı; bunu yaparken Sumner’ın, her maksimal eşlemenin her köşeyi kapsayan mükemmel (perfect) bir eşleme olduğu çizgeler hakkında kanıtladığı bir olguya dayandı.

Tek sayıda köşede hiçbir eşleme mükemmel değildir ve birçok çizgede her maksimal eşleme tam olarak bir köşeyi dışarıda bırakır: modelin argümanı uyarlanamadı. Yazarlar eşitlik durumu için her n için geçerli farklı bir kanıt buldu ve makaleyi kendileri yazdı; GPT-6 Astra’dan geçirilen son bir okuma “birkaç küçük düzeltmeye” yol açtı. Makale henüz hakem değerlendirmesinden geçmemiş bir ön baskı ve argümanın bilgisayarla doğrulanmış bir sürümünden söz etmiyor.

1907’ye dönüş

Bir çizge tavana eşit kenar sayısına ulaşırsa, temel eşitsizlik her maksimal eşleme için eşitliğe dönüşür. Eşlemeleri akıllıca seçen yazarlar, böyle bir çizgenin ya bir yıldız — bir köşe öteki tüm köşelere bağlı, başka hiçbir şey yok — olduğunu ya da hiç kritik kenar-olmayanı bulunmadığını gösteriyor. Çap-2-kritik bir çizgede bir üçgenin her kenarı bir kritik yol üzerinde bulunur; dolayısıyla kritik kenar-olmayan yoksa üçgen de yoktur; yıldızda da üçgen yoktur. Tavana ulaşan bir çizge bu yüzden üçgensizdir ve son adım, varsayımın güçlendirmeye giriştiği teoremdir: dengeli tam iki parçalı çizgeyi tavanda tek başına bırakan, Mantel’in 1907 tarihli sonucu.