MatematikaPracetakTeori3 menit baca

BUKTI DARI AI, DIGAMBAR ULANG UNTUK MANUSIA

Gambarlah beberapa titik dan hubungkan sebagian dengan garis. Matematikawan menyebutnya graf; titik-titiknya adalah simpul, garis-garisnya sisi, dan jumlah garis yang menyentuh suatu titik adalah derajat-nya. Pohon adalah graf tanpa putaran (loop) yang menyatu dalam satu bagian, seperti ranting bercabang; pohon dengan t titik selalu punya t − 1 garis.

Pada awal 1960-an, Paul Erdős dan Vera T. Sós mengajukan pertanyaan sederhana: berapa banyak garis yang memaksa sebuah graf memuat setiap pohon dengan ukuran tertentu? Jawaban mereka, konjektur Erdős–Sós, adalah sebagai berikut:

Jika sebuah graf memiliki derajat rata-rata lebih besar dari t − 2, graf itu memuat setiap pohon dengan t simpul.

Ambang ini tajam. Ambil beberapa salinan terpisah dari graf lengkap dengan t − 1 titik, setiap pasangnya terhubung: setiap titik punya tepat t − 2 tetangga, tetapi tidak ada bagian yang cukup besar untuk memuat pohon dengan t titik. Kesulitannya ada pada kata rata-rata. Jika setiap titik punya setidaknya t − 1 tetangga, kita dapat menempatkan pohon cabang demi cabang tanpa masalah. Namun rata-rata tidak mengatakan apa pun tentang titik individual: sebagian bisa punya ratusan tetangga, yang lain hampir tidak punya.

Enam puluh tahun jawaban parsial

Menurut sejarah yang diceritakan dalam makalah, masalah ini berasal dari tahun 1962–1964 dan menjadi pusat cabang matematika yang mempelajari berapa banyak sisi yang memaksa munculnya suatu pola tertentu. Kasus-kasus khusus satu per satu terpecahkan: bintang, lintasan, bintang ganda, pohon dengan sedikit cabang. Pada awal 1990-an, empat matematikawan — Ajtai, Komlós, Simonovits, dan Szemerédi — mengumumkan bukti untuk pohon yang sangat besar, tetapi makalah-makalah terbaru mencatat bahwa naskah lengkapnya tidak pernah diterbitkan. Hasil parsial lain menyusul pada 2021, 2024, dan 2026. Pada 4 September 2026, Reed dan Stein mengunggah bukti untuk graf besar yang padat, yang menurut mereka dikembangkan tanpa AI.

Lalu datang sebuah laporan. Pada September 2026, Tom Adamczewski dan Thomas Bloom, dalam dokumen berjudul FrontierMath Erdős, mengkreditkan bukti konjektur lengkap kepada versi pra-rilis sebuah model AI, GPT-6 Astra. Argumen pencacahan aslinya terbuka untuk umum, dan sebuah repositori pendamping mencatat pencarian bukti secara otonom oleh AI tersebut serta verifikasi formal dalam bahasa pemeriksa bukti Lean. Para penulis laporan juga mengimbau para pakar manusia untuk menulis uraian yang lebih lengkap dan tradisional.

Membuka graf satu titik demi satu titik

Jay Cummings, dari California State University, Sacramento, menjawab imbauan itu. Artikelnya sepanjang 27 halaman mempertahankan argumen pencacahan inti dari AI, tetapi mengubah cara menceritakannya:

  1. Buka graf secara bertahap. Urutkan simpul-simpul dalam suatu urutan dan buka satu per satu, bersama sisi-sisi di antara simpul yang sudah tampak.
  2. Minta lebih banyak. Alih-alih sembarang salinan pohon, carilah salinan yang “akar” pilihannya terletak tepat di simpul pertama. Meminta lebih banyak justru membuat buktinya lebih mudah.
  3. Hitung tetangga awal. Ini adalah tetangga simpul pertama yang muncul sebelum salinan seperti itu muncul. Jumlahkan mereka atas semua urutan yang mungkin.
  4. Batasi totalnya. Dengan menukar simpul atau seluruh blok dalam urutan — langkah yang selalu bisa dibatalkan — Cummings menunjukkan bahwa, rata-rata atas semua urutan, ada paling banyak t − 2 tetangga awal.

Langkah terakhirnya singkat. Jika graf tidak memuat salinan pohon itu, setiap tetangga simpul pertama akan menjadi tetangga awal, dalam setiap urutan. Dirata-ratakan atas semua urutan, itu tepat sama dengan derajat rata-rata — yang menurut asumsi melebihi t − 2. Kontradiksi: pohon itu pasti ada.

Bukti ini hanya memakai total derajat, bukan cara derajat itu tersebar. Cummings juga memberikan versi probabilistik, dan mengerjakan contoh pohon dengan empat dan lima simpul pada graf konkret.

Bukti dalam bentuk buku bergambar

Artikel ini memuat 32 gambar. Ia ditutup dengan sebuah konsekuensi klasik: warnai semua garis graf lengkap dengan q warna, maka salah satu warna akan selalu memuat pohon tertentu begitu graf memiliki q(t − 2) + 2 simpul. Dalam pernyataan penutup, Cummings menjelaskan bahwa ia mengembangkan teks ini lewat dialog panjang dengan ChatGPT, bahwa gagasan penyajian baru — tetangga awal, partisi eksplisit, gambar-gambar — adalah miliknya, dan bahwa ia telah memeriksa semuanya serta bertanggung jawab penuh.

Ia membandingkan uraiannya dengan uraian terbaru lainnya oleh Riordan dan Scott, Wood, serta Frederickson, dan mencatat bahwa metode ini sudah diperluas ke jaringan berarah dan ke “hipergraf”, sebagian perluasan itu juga dikreditkan kepada GPT-6 Astra. Kontribusinya, tulisnya, adalah “eksposisi visual argumen yang berpusat pada pembaca, bukan penyelesaian baru atas konjektur tersebut.”