AI MEMECAHKAN TEKA-TEKI PEWARNAAN

Ambil sebuah jaringan titik yang dihubungkan garis — yang oleh matematikawan disebut graf. Sekarang warnai titik-titiknya sehingga dua titik yang dihubungkan garis tidak pernah berwarna sama. Jumlah warna terkecil yang memungkinkan hal itu adalah bilangan kromatik graf tersebut. Kasus khusus yang terkenal adalah teorema empat warna, terbukti pada 1977, yang judulnya sudah menjelaskan segalanya: “Every planar map is four colorable” (setiap peta bidang dapat diwarnai dengan empat warna).

Taruhan Hadwiger pada 1943

Pada 1943, Hadwiger mengajukan aturan menyeluruh untuk semua graf. Kecilkan sebuah graf dengan menghapus titik atau garis, dan dengan meleburkan dua titik yang terhubung menjadi satu. Hasilnya disebut minor. Hadwiger melihat graf lengkap terbesar — gugus tempat setiap titik terhubung ke semua titik lainnya — yang bisa diperoleh dengan cara ini, dan menduga bahwa jumlah warna yang diperlukan tidak pernah melebihi ukuran gugus itu.

Makalah ini menyebutnya “salah satu masalah tertua dan paling mendasar dalam teori graf”. Dugaan itu hanya terbukti untuk kasus kecil: hingga gugus berukuran lima, yang ternyata setara dengan teorema empat warna atau dapat direduksi kepadanya. Mulai dari enam, masih terbuka.

Makin dekat, satu logaritma demi satu logaritma

Karena pernyataan persisnya sulit ditaklukkan, para peneliti mencoba membatasi jumlah warna dengan suatu fungsi dari ukuran gugus, yang tumbuh selambat mungkin. Makalah ini menceritakan kemajuannya. Selama puluhan tahun, batas terbaik tumbuh sedikit lebih cepat daripada sebanding — dengan faktor yang melibatkan akar kuadrat dari sebuah logaritma. Beberapa tahun lalu, Norin, Postle, dan Song menembus penghalang itu. Delcourt dan Postle kemudian memperbaikinya lagi dan, yang terpenting, menunjukkan bahwa cukup menangani graf yang cukup kecil. Liu dan Luo menekan faktor tambahannya hingga menjadi logaritma rangkap tiga.

Titik akhir alaminya adalah dugaan Hadwiger linear: kelipatan tetap dari ukuran gugus selalu cukup. Itulah yang kini diklaim telah dibuktikan oleh Sergey Norin dari McGill University di Montreal dan Raphael Steiner dari ETH Zurich.

Peran mesin

Para penulis berterus terang: bukti itu ditemukan oleh GPT-6 Astra, model OpenAI, mengikuti arahan mereka. Mula-mula mereka memintanya membuktikan kasus graf yang sangat padat, yang mereka yakini sebagai kepingan yang hilang. Model itu berhasil, tulis mereka, “hanya setelah beberapa jam dan sedikit dorongan semangat”. Ketika diminta membuat satu ketergantungan menjadi eksplisit, ia mencakup graf hingga ukuran tertentu — tetapi belum sepenuhnya rentang yang dibutuhkan. Mereka lalu memintanya memberi gagasan orisinal untuk menjembatani celah itu, yang menghasilkan langkah “bootstrap” dalam bukti akhir. Hampir tidak ada gagasan pembuktian spesifik milik para penulis sendiri yang bertahan, kata mereka, kecuali satu saran tentang kontraksi.

Tulisannya dibuat manusia. Model OpenAI lainnya membantu pengoreksian dan daftar pustaka. Para penulis melaporkan bahwa Codex dari OpenAI menghasilkan versi formal yang dapat diperiksa mesin dari seluruh bukti di asisten pembuktian Lean, yang diunggah daring bersama draf awal tulisan AI. Mereka memikul tanggung jawab penuh atas matematikanya.

Di dalam pembuktian

Argumennya terdiri dari dua bagian:

1. Graf kecil, sedikit warna. Untuk graf yang tidak jauh lebih besar dari batas gugus, para penulis menunjukkan bahwa sekitar empat kali ukuran gugus sudah cukup. Titik awalnya adalah hasil Reed dan Seymour tahun 1998: bentuk pewarnaan yang dilonggarkan, “pecahan” (fractional), sudah mematuhi aturan linear dengan faktor dua. Karya baru ini mengubah pewarnaan pecahan menjadi pewarnaan sungguhan dengan menambahkan beberapa garis ekstra ke graf dan menemukan pemasangan (matching) yang sangat besar dalam sebuah struktur bantu.
2. Sebuah bootstrap. Argumen kedua memperluas rentang ukuran graf yang tercakup dengan faktor empat pertiga pada eksponen di setiap langkah, dengan imbalan konstanta yang lebih besar. Sepuluh langkah membawa rentang itu dari sepertiga hingga sekitar 5,92, melewati ambang 5 yang dipersyaratkan reduksi Delcourt-Postle. Bagian ini memakai trik lama dari Gyárfás, yang menurut para penulis belum pernah diterapkan pada masalah ini.

Para penulis menggambarkan bukti itu sebagai dibangun dari perkakas yang sudah dikenal — “terkandung dalam selubung cembung hasil-hasil yang ada”, namun tidak di tepinya yang jelas.

Yang masih terbuka

Konstantanya luar biasa besar: perkiraan kasar memberikan sekitar 10¹⁰⁰. Para penulis melihat ruang untuk menurunkannya di bawah 10¹⁰, tetapi menurut mereka mencapai, katakanlah, 100 memerlukan gagasan baru. Dugaan persis Hadwiger tidak tersentuh: “Kami belum memutuskan,” tulis mereka. Makalah ini adalah pracetak; 41 halaman matematika baru kini akan menghadapi pemeriksaan para ahli lain.