1960'LARDAN KALMA BİR ÇİZGE BULMACASI SONUNDA ÇÖZÜLÜYOR

Birkaç nokta alın ve bazı nokta çiftlerini çizgilerle birleştirin: matematikçiler buna çizge (graph), noktalara köşe, çizgilere de kenar der. Bir döngü (cycle), farklı köşeleri ziyaret edip başladığı yere dönen kapalı bir yoldur. Doğal bir soru, bir çizgenin kenarlarının — her kenar tam bir kez kullanılarak — döngülere ayrılıp ayrılamayacağıdır.

Makalenin hatırlattığı gibi, cevap uzun zamandır biliniyor: bu, ancak ve ancak her köşe çift sayıda kenara değdiğinde mümkündür. Bu tür çizgelere Euler çizgesi (Eulerian) denir. Sıradaki soru, kaç döngüye ihtiyaç olduğudur. Ve yalnızca döngülerin yetmediği çizgeler için, tekil kenarlar da parça olarak kabul edilir.

Sanı

1960’larda Erdős ve Gallai, n köşeli her çizgenin kenarlarının, n ile en fazla orantılı sayıda — O(n) diye yazılır — döngüye ve tekil kenara ayrılabileceğini öne sürdü. Erdős bunu açık problem derlemelerinin birkaçına dahil etti. Hajós’un ilgili bir sanısı ise her Euler çizgesinde en fazla (n − 1)/2 döngü olmasını ister.

Doğrusal sınır, umulabilecek en iyisidir: Erdős bazı çizgelerin yaklaşık 1,5 n parçaya ihtiyaç duyduğunu gösterdi. Soru, n’nin bir sabit katının her zaman yetip yetmediğiydi.

Elli yıllık ağır ağır ilerleyen sınırlar

Erdős ve Gallai’nin kendileri basit bir yöntem fark etti: en uzun döngüyü tekrar tekrar çıkarmak. Bu yaklaşık n log n parça verir — ve makaleye göre bu, neredeyse elli yıl boyunca en iyi genel sınır olarak kaldı. Daha yakın zamanda Conlon, Fox ve Sudakov bunu n log log n’ye, ardından Bucić ve Montgomery n log* n’ye indirdi; burada log* n — birin altına inmek için kaç kez logaritma almak gerektiği — akıl almaz derecede yavaş büyür. Bu yaklaşımlar turlar hâlinde çalışıyordu ve her tur yaklaşık n döngüye mal oluyordu; dolayısıyla tur sayısı her zaman nihai sayıma sızıyordu. Sanı, rastgele çizgeler gibi özel aileler için de kanıtlanmıştı.

Döngülerin bedelini ödeyen ağırlıklar

Güney Kore’deki KAIST’ten Jaehoon Kim şimdi sanıyı kanıtlıyor: n köşeli her çizgenin en fazla Cn döngüye ve kenara ayrıldığı sabit bir C vardır. Bir sonuç olarak, Hajós’un sanısı da bir sabit çarpana kadar doğrudur.

Kanıt turlardan vazgeçiyor. Tek bir prosedür döngüleri ve kenarları birer birer çıkarıyor ve toplam, her biri n’nin bir sabit katının altında kalan iki nicelikle kontrol ediliyor.

• Derecelere dayalı bir potansiyel. Her köşe, kenar sayısı arttıkça küçülen bir ağırlık alır, kabaca 1 / (derece × log² derece). Köşelerinin ağırlıkları toplamı en az 1 olan bir döngü ağırdır. Ağır bir döngüyü çıkarmak, genel bir “potansiyeli” en az 1 düşürür ve bu potansiyel, n’nin bir sabit katından fazla olmayan bir değerle başlar. Bu yüzden ağır döngüler yalnızca O(n) kez çıkarılabilir.
• Köşe sayısı. Hiç ağır döngü kalmadığında çizge “hafiftir” — ve yeni ana teorem, büyük dereceli hafif bir çizgenin yoğun, neredeyse kapalı bir bölge içermesi gerektiğini gösteriyor. Bu bölge, boyutuyla orantılı sayıda döngüye ve kenara ayrılır; ardından köşelerinin en az ellide biri en fazla iki kenarla kalır ve kalıcı olarak devre dışı kalır. Her köşe yalnızca bir kez devre dışı kalabileceğinden, bu kısım da O(n)’e mal olur.

Çizgenin yoğun kısımlarında, yol parçaları “genişleticiler” (expanders) üzerinden geçen birleştirme yollarıyla tek bir döngüde kapatılır; rastgele bir boyama, aynı döngünün birleştirme yollarını birbirinden uzak tutar. — Figure 3, Kim (2026), arXiv:2610.07840.

Kanıt, bu yoğun bölgeleri ayırmak için Bucić ve Montgomery’nin sağlam “genişleticiler” — her köşe kümesinin çok sayıda komşusu olduğu çizgeler — araç takımını genişletiyor ve aynı döngünün bağlantı yolları asla çakışmasın diye köşeleri rastgele boyuyor.

Hâlâ açık olanlar

C sabiti devasa ve yazar onu optimize etmeye çalışmadı. En iyi sabiti — en az 1,5 — bulmak hâlâ açık bir sorun; tam Hajós sanısı ve Gallai’nin çizgeleri yollara ayırmaya ilişkin ilgili sanısı da öyle. Ağırlıklandırma hilesi yalnızca toplamı yakınsayan ağırlıklar gerektiriyor ve yazar bunun başka ayrıştırma problemlerinde de işe yarayabileceğini öne sürüyor.

Bu, tek yazarlı ve henüz hakem değerlendirmesinden geçmemiş bir ön baskı.

Çıkar çatışması. Yazar, argümanları geliştirirken ve metni ile şekilleri hazırlarken ChatGPT (OpenAI) ve Claude’u (Anthropic) yoğun biçimde kullandığını, tüm sonuçları doğruladığını ve makalenin tüm sorumluluğunu üstlendiğini belirtiyor. Okuduğunuz metin de Claude tarafından yazıldı.