BİR YAPAY ZEKÂ 1990’LARDAN KALMA BİR BOYAMA SANISINI BATIRIYOR

Çizgilerle birbirine bağlanmış noktalardan oluşan bir ağ alın — bir çizge (graph). Bir tam boyama (total colouring), üç kurala uyarak her noktaya ve her çizgiye bir renk verir: komşu iki nokta farklı olur, bir noktada buluşan iki çizgi farklı olur ve bir çizgi iki uç noktasından farklı olur. İşe yarayan en küçük renk sayısına tam renk sayısı (total chromatic number) denir ve χ″(G) diye yazılır.

Şimdi işi zorlaştıralım. Her noktaya ve her çizgiye izin verilen renklerin kendi listesini verin; tüm listeler aynı k boyutunda olsun ve listelerden seçilmiş geçerli bir boyama isteyin. Listeler ne olursa olsun işe yarayan en küçük k, liste tam renk sayısıdır, χ″ℓ(G). Hiçbir zaman χ″(G)’den küçük olamaz: tüm listeler aynıysa sıradan probleme geri dönülür.

1990’ların sonundan bir sanı

Üç grup — Borodin, Kostochka ve Woodall; Juvan, Mohar ve Škrekovski; Hilton ve Johnson — 1990’ların sonunda birbirinden bağımsız olarak, kişisel listelerin hiçbir şeye mal olmadığını öne sürdü:

her çizge için (iki nokta arasında birden çok çizgi olsa bile) χ″ℓ(G) = χ″(G).

Bu, Liste Tam Boyama Sanısıdır (List Total Colouring Conjecture). Kanıtlar onu destekliyordu: hiçbir noktada ikiden fazla çizgi olmayan çizgeler için geçerli ve her noktasında tam olarak üç çizgi bulunan her çizgenin (kübik çizge) listelerden en fazla 5 renge ihtiyaç duyduğu biliniyordu.

Karşı örnek

Kanada’daki Victoria Üniversitesi’nden Jonathan Noel, χ″ = 4 ama χ″ℓ = 5 olan 20 noktalı kübik bir çizge gösteriyor. Sanı yanlış.

Yapı derli toplu. K₂,₃ adlı küçük bir çizgenin dört kopyasını alın: her biri aynı üç “uç” (terminal) noktaya bağlı iki “özel” nokta. Sonra her kopya çiftini uçlar arasındaki tam olarak bir “çapraz” çizgiyle bağlayın. Her noktada sonunda üç çizgi olur.

Yalnızca dört renkle tam boyanmış G çizgesi; renkler şekiller ve çizgi stilleriyle gösteriliyor. — Şekil 1, Noel (2026), arXiv:2609.38417.

Sıradan oyunda dört renk yeter: 4. renk, birbirine hiç değmeyen tüm özel noktalara ve tüm çapraz çizgilere gider; geri kalanı küçük bir tablo ve döngüsel bir kural halleder.

Karşılanamayan listeler

Tuzak 1’den 5’e kadar renkleri kullanıyor. i bloğunun her noktası ve çizgisi “i dışındaki tüm renkler” listesini alıyor; çapraz çizgiler ise 5’i ya da i + 2’yi içermeyen özenle seçilmiş listeler alıyor. Kanıt sonra kısa bir polisiye gibi ilerliyor:

• Lemma: K₂,₃’ün herhangi bir 4 renkli boyamasında iki özel noktanın rengi aynı olmalı.
• Böylece her i bloğunun bir renk çifti {i, sᵢ} var ve iki blok arasındaki her çapraz çizgi, iki çiftin ortak bir rengini kullanmalı.
• Biraz sayma, tek bir t renginin dört çiftin hepsine ait olması gerektiğini gösteriyor.
• Her olası t için, belirli bir çapraz çizgi o rengin listesinde olmadığını görüyor. Çelişki.

Liste ataması: her nokta ve çizgi, belirtilen dışında 1’den 5’e kadar her rengi kullanabilir. Hiçbir tam boyama bu listelere uyamaz. — Şekil 2, Noel (2026), arXiv:2609.38417.

Makine buldu, matematikçi denetledi

Makale, kökeni konusunda alışılmadık derecede açık sözlü. 24 Eylül 2026’da Noel, ChatGPT 6 Astra Ultra’ya sanıyı çürütmesi talimatını verdi ve model karşı örneği üretti, “yazardan çok az katkıyla”. Noel argümanları denetledi ve metni modelin ürettiği taslaklardan yeniden yazdı; model ayrıca düzeltmelere yardım etti, kaynak önerdi ve şekilleri çizdi. Beyan şöyle bitiyor: “Doğruluğun tüm sorumluluğu yazara aittir.” Makale bir ön baskı, ama kanıt, sabırlı her okuyucunun doğrulayabileceği kadar kısa.

Bir farkı mı, daha fazlası mı?

Kişisel listeler bir fazladan renge mal olabiliyor. Daha fazlasına mal olabilirler mi? Üçlük bir fark, iyi incelenmiş bir akrabayı, Liste Kenar Boyama Sanısını da devirirdi, çünkü χ″ℓ ≤ χ′ℓ + 2 ve χ″ ≥ χ′. Noel, yapay zekânın karşı örneğinin ayakta bıraktığı açık bir soruyla bitiriyor: her çizge için χ″ℓ(G) ≤ χ″(G) + 1 mi?