HER HARİTA İÇİN DÖRT RENK, DOĞRUSAL ZAMANDA BULUNDU

Düz bir kâğıda çizilmiş her harita, komşu ülkeler asla aynı rengi paylaşmayacak şekilde dört renkle boyanabilir. Francis Guthrie bunu 1852’de bir varsayım olarak ortaya attı; Appel ve Haken 1976’da kanıtladı. Ama teorem yalnızca dört rengin var olduğunu söylüyor. Belirli bir harita için bunlar nasıl bulunur? Tokyo Üniversitesi’nden Yuta Inoue ile Japonya, Kanada, Slovenya ve Danimarka’dan beş meslektaşı “Kolay bir yanıt yok” diye yazıyor. Konu o kadar karışıktı ki pek çok karşı örnek önerisine yol açtı.

Noktalar, çizgiler ve üçgenler

Her ülke bir nokta, yani bir köşe (vertex) olur; her ortak sınır da bir çizgi, yani bir kenar (edge): harita, çizgileri kesişmeden çizilen bir düzlemsel çizge (planar graph) haline gelir. Onu boyamak, her köşeye dört renkten birini, her kenarın iki ucunda farklı olacak şekilde vermek demektir. Köşe sayısına n diyelim. Her yüzün bir üçgen olduğu üçgenlemeleri (triangulations) ele almak yeterlidir: daha fazla kenar boyamayı yalnızca zorlaştırır.

Kempe’nin değiş tokuşu

Temel hamle A. B. Kempe’nin 1879 tarihli bir makalesine dayanır. Dört rengi çiftler halinde eşleştirin, örneğin kırmızıyı maviyle, yeşili sarıyla. Bir Kempe zinciri (Kempe chain), bir çiftin iki rengini taşıyan, birbirine bağlı bir köşe grubudur. Bu iki rengin yerini tüm bir zincir boyunca değiştirmek boyamayı geçerli tutar.

Etrafında sırayla v0’dan v3’e dört komşusu olan bir v köşesi alın ve önce geri kalanı boyayın. Komşular üç ya da daha az renk kullanıyorsa v boşta kalan rengi alır. Dördünü de kullanıyorlarsa, v0’dan başlayan, v0 ile v2’nin renklerindeki zinciri izleyin. Zincir v2’ye ulaşmıyorsa yer değiştirin: v0, v2’nin rengini alır ve v için bir renk boşalır. v2’ye ulaşıyorsa, bunun yerine v1’in, v1 ile v3’ün renklerindeki zincirinde yer değiştirin; böylece v1, v3’ün rengini alır.

Her zaman onarılabilen parçalar

Teoremin kanıtları indirgenebilir yapılandırmalara (reducible configurations) dayanır: kesilip çıkarılabilen, geri kalan boyandıktan sonra yeniden yerine konabilen küçük desenler. Halkalarının (ring) — hemen çevrelerindeki köşelerin — renkleri uymazsa, dışarıda yapılan sınırlı sayıda iyileştirici Kempe değişikliği onları her zaman düzeltir: burada kullanılan, halkaları en fazla 18 köşeli desenler için en fazla 25.

Sayılarla etiketlenmiş yedi noktadan oluşan küçük bir çizge ve aynı çizgenin daha büyük bir üçgen ağıyla çevrili hali.

İndirgenebilir bir yapılandırma (solda; her sayı, o köşenin tam haritada sahip olması gereken komşu sayısıdır) ve aynı desenin R halkasıyla tamamlanmış hali (sağda). — Şekil 1, Inoue ve ark. (2026), arXiv:2610.39753.

Robertson, Sanders, Seymour ve Thomas 1997’de bu yolla, her seferinde bir desen olmak üzere, nasıl boyama yapılacağını gösterdi. Her tur çizgeyi birkaç köşe küçültür ve tamamının taranmasına mal olur; bu yüzden süre karesel (quadratic) büyür: iki kat büyük bir harita için dört kat uzun.

Önceki bir makalede (FOCS’26) aynı altı yazar, her üçgenlemenin, 8.202 desenlik bir listeden alınmış, n ile orantılı sayıda birbirine değmeyen indirgenebilir yapılandırma içerdiğini — ya da her iki yanında köşe bulunan, aynı işe yarayan o kadar sayıda kısa döngü — kanıtladı. Tüm desenleri bir kerede çıkarıyor, geri kalanı boyuyor, sonra tüm halkaları birlikte onarıyorlar. Rastgele bir Kempe değişikliği, doğru renk eşleşmesini (üçte bir şans) ve halkaya değen her zincirde doğru yazı turayı (her biri için ikide bir şans) seçerse belirli bir halkaya yardım eder. Bu tür en fazla 18 zincirle bu, en az 3 × 2¹⁸, yani 786.432’de bir şans eder: küçük ama sabit. Dolayısıyla tur sayısı yalnızca log n gibi, kabaca n’nin kaç kez ikiye bölünebileceği kadar büyür. Ama tek bir değişiklik çizgenin sabit bir oranını içerebilir: her biri tam bir taramaya mal olur, toplamda n log n.

Tarama yerine tablo

Yeni makale log n değişikliği koruyor ama her birini ucuzlatıyor. n ile orantılı süren bir hazırlıktan sonra her değişiklik ortalama yaklaşık n / log n adımda bulunup uygulanıyor. log n değişiklik birlikte böylece n ile orantılı bir süre — doğrusal zaman (linear time) — alıyor; yazarlar bu sınırın optimal olduğunu söylüyor.

Hile “Dört Rus Yöntemi”nde (Method of Four Russians). ½ log n bitlik bir koda — n’yi yazmak için gereken ikili basamakların yarısına — sığan bir alt problemin en fazla √n olası sürümü vardır; bu yüzden tüm yanıtları önceden hesaplanıp bir tabloda saklanabilir. Varsayılan bilgisayar, yaklaşık log n bitlik bellek sözcükleriyle, saklanan herhangi bir yanıtı tek adımda okur.

Çizge, kısa sınırları olan iç içe bölgelere tekrar tekrar kesilir. En küçükleri yaklaşık log n köşe içerir ve renkleriyle birlikte tek bir koda sığar. Her bölge için küçük bir özet çizge, hangi sınır köşelerinin bir Kempe zincirini paylaştığını kaydeder. Bir değişiklik sonra “değiştir” ya da “koru” bitlerinden oluşan diziler halinde aşağı iner ve her küçük bölgede tek bir bakış her rengi günceller.

Kırmızı, mavi, yeşil ve sarı noktalardan oluşan renkli bir çizge; gri bir bölgenin sınırı çizilmiş, bazı kenarlar kalın siyahla çizilmiş.

Dört renkle boyanmış bir çizgenin bir parçası. Gri alan bir R bölgesidir; kalın siyah kenarlar kırmızı-mavi ve yeşil-sarı çiftlerinin Kempe zincirlerine aittir. — Şekil 2, Inoue ve ark. (2026), arXiv:2610.39753.

Aynı bölge sınırı; sınır noktaları ince mavi çizgilerle birkaç açık mavi lekeye bağlanmış.

Aynı bölgenin özeti: her mavi leke bir Kempe zinciri parçasını temsil eder ve çizgileri hangi sınır köşelerini bağladığını gösterir. — Şekil 3, Inoue ve ark. (2026), arXiv:2610.39753.

Zar atmadan seçmek

Rastgele seçimlerle bu yöntem bir haritayı zaten ortalamada doğrusal zamanda boyuyor. Hızdan ödün vermeden zarları ortadan kaldırmak “açık ara en zorlu kısım” oldu. Şimdiye kadarki her karar onun lehine çıktığı sürece bir halkaya canlı diyelim. Ona değen u kararlaştırılmamış zincir yazı turaya bırakılsaydı, halka 1/2^u olasılıkla hayatta kalırdı; tüm canlı halkalar üzerinden toplandığında bu sayılar beklenen hayatta kalan sayısını verir. Bir zincir hakkında karar vermek, o seçimi isteyen her halkanın terimini ikiye katlar, diğerlerininkini sıfırlar. Algoritma toplamın düşmesini engelleyen seçeneği alır; böylece sonunda en az, şansın ortalamada yardım edeceği kadar halkaya yardım edilmiş olur.

Bir kronometre değil, bir sınır

Makale hiçbir uygulama (implementation) ya da çalışma süresi bildirmiyor ve “n ile orantılı” ifadesinin içinde gizli sabitler verilmiyor. Bunlar büyük: 8.202 desenin her biri için algoritma, halkasının her boyamasının kaç iyileştirici değişikliğe ihtiyaç duyduğunu saklıyor — “devasa, sabit miktarda bilgi”. Yazarlar bir ekte, üzerine inşa ettikleri 2013 tarihli bir iç içe bölge yapımındaki “küçük bir hatayı” da düzeltiyor. 1852’den kalma bir varsayım artık, maliyeti boyadığı haritadan daha hızlı büyümeyen bir boyama yöntemiyle birlikte geliyor.