JARINGAN ACAK TAK LAGI BISA DIWARNAI PADA SATU KEPADATAN TETAP
Ambil sebuah graf — titik-titik yang dihubungkan oleh tautan — dan sekotak warna. Sebuah pewarnaan sejati (proper colouring) dengan q warna memberi setiap titik salah satu dari q warna sehingga dua titik yang terhubung tidak pernah memiliki warna yang sama. Dengan sedikit tautan, hal itu mudah. Dengan banyak tautan, hal itu menjadi mustahil.
Sekarang bangun graf itu secara acak: n titik, setiap pasang dihubungkan secara independen dengan peluang kecil, sehingga sebuah titik rata-rata memiliki d tetangga. Seiring d bertambah, graf acak itu beralih dari “hampir pasti dapat diwarnai dengan q warna” menjadi “hampir pasti tidak”. Di mana tepatnya peralihan itu terjadi? Pertanyaan itu, untuk berapa pun jumlah warna q yang tetap mulai dari tiga, adalah pokok sebuah makalah baru karya Gaia Carenini, di University of Cambridge.
Peralihan yang mungkin bergoyang
Dalam sebuah makalah dari tahun 1999 yang tercantum dalam daftar pustaka, Achlioptas dan Friedgut membuktikan bahwa transisi itu tajam: untuk setiap ukuran n, ada derajat rata-rata kritis d_q(n) sedemikian sehingga sedikit di bawahnya, graf itu hampir pasti dapat diwarnai, dan sedikit di atasnya, hampir pasti tidak. Jendela tempat peralihan itu terjadi menyusut hingga lenyap.
Namun hal itu menyisakan celah. Tak ada yang mencegah nilai kritis itu sendiri berosilasi seiring graf makin besar — berada di satu tempat untuk graf berukuran tertentu, sedikit bergeser untuk graf yang lebih besar, dan tak pernah menetap. Konjektur konvergensi Achlioptas–Friedgut menyatakan bahwa hal ini tidak terjadi: untuk setiap q, ada satu konstanta d_q, yang di bawahnya graf acak dapat diwarnai dan di atasnya tidak.
Apa yang diramalkan para fisikawan
Fisika statistik punya gambaran tentang apa yang terjadi. Seiring tautan ditambahkan, pewarnaan-pewarnaan yang sah mengelompok menjadi gugus (clusters): pewarnaan dalam satu gugus saling mirip, sedangkan dua gugus berbeda pada banyak titik. Lalu, pada tahap yang disebut kondensasi, segelintir gugus besar memuat bagian yang cukup besar dari semua pewarnaan — dan baru kemudian himpunan pewarnaan itu menjadi kosong. Pengorganisasian itu menjelaskan mengapa argumen pencacahan kesulitan di dekat ambang.
Untuk banyak warna, penelitian sebelumnya telah menjepit ambang itu ke dalam rentang yang sempit: ambang itu terletak antara sekitar 2q log q − log q − 2 log 2 dan 2q log q − log q − 1, celah selebar 2 log 2 − 1 seiring q bertambah. Namun “sempit” tidak sama dengan “tetap”, dan untuk jumlah warna yang kecil seperti tiga, pertanyaan itu tetap terbuka.
Masalah kembar, ditangani lebih dulu
Pewarnaan memiliki kembaran: keterpenuhan (satisfiability), yaitu masalah memilih nilai benar atau salah untuk variabel-variabel sehingga sederet batasan logika acak semuanya terpenuhi. Di sana pun, ambang yang tajam diketahui ada tanpa bukti bahwa ambang itu menetap. Dalam sebuah laporan dari tahun 2026 yang dikutip dalam makalah itu, Carenini mengumumkan bukti bahwa ambang itu memang menetap, untuk setiap panjang batasan mulai dari tiga, dengan menunjukkan bahwa jendela transisinya sangat sempit. Makalah baru ini mengadaptasi argumen tersebut untuk pewarnaan.
Pasangan yang membeku bersama
Bukti itu berjalan melalui serangkaian reduksi. Dengan menambahkan tautan acak satu per satu, misalkan H adalah saat graf itu berhenti dapat diwarnai. Jika H hanya sedikit berubah dari satu graf acak ke graf acak lainnya — dalam jendela sekitar n/(log n)² tautan — maka ambang itu pasti menetap. Sebuah ketaksamaan klasik mengubah hal itu menjadi pertanyaan tentang graf terakhir yang masih dapat diwarnai: rata-rata, berapa banyak tautan acak baru yang dapat ditahannya?
Di sinilah gagasan kuncinya: pasangan beku (frozen pairs). Dua titik membentuk pasangan beku ketika setiap pewarnaan yang sah memberi keduanya warna yang sama. Sebuah tautan baru berakibat fatal tepat ketika tautan itu menghubungkan pasangan semacam itu. Titik tunggal tidak dapat dibekukan pada satu warna tertentu, karena menukar-nukar warna selalu menghasilkan pewarnaan sah yang lain; yang dipaksakan adalah hubungan antara dua titik. Carenini melacak bagaimana kelas-kelas beku ini tumbuh seiring tautan ditambahkan, dengan menghapus satu tautan atau satu titik utuh dan mengamati pilihan-pilihan yang muncul kembali. Estimasi-estimasinya menunjukkan bahwa graf terakhir yang dapat diwarnai tidak dapat bertahan lama, sehingga jendela itu cukup menyempit untuk membuktikan konjektur tersebut.
Apa yang masih belum diketahui
Teorema itu menyatakan bahwa ambang d_q ada untuk setiap q ≥ 3. Teorema itu tidak menyatakan di mana letaknya: makalah itu tidak memberikan nilainya, bahkan untuk tiga warna. Makalah ini adalah pracetak dengan satu penulis dan belum ditelaah sejawat. Makalah itu diakhiri dengan pernyataan singkat bahwa tak satu pun argumen matematisnya dihasilkan oleh model bahasa besar.
