HUBUNGKAN SETIAP TITIK DENGAN SEMUA TITIK LAIN: PERSILANGAN PALING SEDIKIT, TERBUKTI

Letakkan lima titik di selembar kertas dan hubungkan setiap pasangan dengan sebuah kurva: sepuluh kurva seluruhnya. Kurva-kurva itu boleh berbelok sesuka Anda, tetapi tidak boleh melewati titik ketiga. Cobalah menghindari setiap persilangan, dan Anda akan gagal. Dengan lima titik, sedikitnya 1 persilangan tak terhindarkan; dengan enam, sedikitnya 3; dengan sepuluh, sedikitnya 60.

Para matematikawan menyebut gambar semacam itu gambaran (drawing) dari graf lengkap Kₙ — n titik, setiap pasangan terhubung — dan jumlah persilangan paling sedikit yang dapat dicapai gambaran mana pun disebut bilangan persilangan (crossing number)-nya. Martin Balko, dari Universitas Charles di Republik Ceko, menyebut pertanyaan ini “salah satu masalah paling terkenal dalam teori graf topologis”.

Hitungan seorang seniman

Pada akhir 1950-an, seniman Inggris Anthony Hill menyusun gambaran Kₙ dengan tepat

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

persilangan, dengan ⌊ ⌋ berarti pembulatan ke bawah. Dugaan bahwa tidak ada gambaran yang bisa lebih baik pertama kali diterbitkan oleh Guy, kemudian dibahas oleh Harary dan Hill, dan dipopulerkan oleh Erdős dan Guy. Dugaan ini dikenal sebagai konjektur Harary–Hill, atau konjektur Guy.

Rumus itu naik dengan cepat:

• 4 titik atau kurang: 0 persilangan
• 5 titik: 1
• 7 titik: 9
• 10 titik: 60
• 14 titik: 315

Enam dekade jawaban parsial

Gambaran dengan tepat Z(n) persilangan sudah ada untuk setiap jumlah titik; bagian sulitnya adalah menunjukkan bahwa tidak ada gambaran yang lebih baik.

Selama lebih dari enam puluh tahun, hal itu hanya terbukti untuk jenis-jenis gambaran khusus — misalnya dengan semua titik pada satu garis dan setiap kurva tetap berada di satu sisi garis itu, atau dengan titik-titik pada bola dan setiap kurva menempuh rute terpendek. Balko sendiri, bersama Fulek dan Kynčl, pernah menuntaskan satu kelas semacam itu. Pada 2021, komputer telah mengonfirmasi rumus itu hingga 14 titik. Untuk jumlah titik yang sangat besar, hasil umum terbaik menjamin sedikitnya 98,5%, lalu 98,99%, dari Z(n).

Sebuah bukti, lalu versi yang lebih jernih

Pada 2026, OpenAI mengumumkan bukti untuk setiap jumlah titik, yang dicantumkan dalam makalah Balko sebagai “OpenAI Math Release preprint” dan diakui sebagai pemilik teorema itu. Makalah itu tidak menyebutkan bagaimana bukti tersebut ditemukan. Menurut Balko, bukti aslinya “relatif pendek”, tetapi “cukup sulit diikuti”. Pracetaknya menyajikan varian yang disederhanakan yang, tulisnya, “hanya memerlukan pengetahuan dasar aljabar linear dan teori graf”. Matematikawan lain, Gelasio Salazar, sedang menyiapkan paparan terpisah yang terperinci.

Menghitung koefisien, bukan persilangan

Karena gambaran yang dikenal sudah mencapai Z(n), hanya batas bawahnya yang perlu dibuktikan. Caranya ada empat langkah.

1. Bilangan ganjil sudah cukup. Gambaran terbaik dapat digambar ulang sehingga kurva-kurva yang berbagi titik tidak pernah bersilangan; setiap persilangan lalu melibatkan 4 titik yang berbeda. Hapus masing-masing dari 6 titik secara bergiliran: setiap gambar 5 titik yang tersisa punya sedikitnya 1 persilangan, dan setiap persilangan bertahan pada tepat 2 dari 6 penghapusan itu (persilangan itu lenyap setiap kali salah satu dari 4 titiknya sendiri dihapus, dan bertahan pada 2 penghapusan lainnya). Jadi dua kali jumlah persilangan sedikitnya 6: sedikitnya 3, yaitu Z(6). Hitungan yang sama berlaku untuk setiap bilangan genap.
2. Sekeluarga polinomial. Beri setiap titik bilangannya sendiri. Sebuah persilangan melibatkan dua kurva, jadi empat titik, jadi empat bilangan. Balko memakai polinomial empat variabel, dipilih sehingga keluarga itu punya tepat Z(n) koefisien yang saling bebas ketika n ganjil — untuk 7 titik, 3 × 3 = 9.
3. Persilangan yang terlalu sedikit menyisakan ruang. Meminta sebuah polinomial bernilai nol di suatu persilangan berarti satu persamaan. Jika persamaannya lebih sedikit daripada koefisien bebasnya, aljabar linear selalu menyisakan solusi tak nol. Jadi gambaran dengan kurang dari Z(n) persilangan akan disertai polinomial tak nol yang bernilai nol di semua persilangannya; ambil yang derajatnya paling rendah.
4. Bidang datar melawan. Geometri masuk melalui satu fakta klasik: sebuah lingkar tertutup di bidang datar memotong lingkar lain dari kanan ke kiri tepat sesering dari kiri ke kanan. Dengan bobot yang dipilih dengan baik, fakta ini menghasilkan jumlah kuadrat dari nilai-nilai polinomial itu, sebagian dihitung positif, sebagian negatif, yang totalnya nol. Suku-suku positif semuanya terletak di persilangan, tempat polinomial itu bernilai nol, sehingga suku-suku negatifnya juga harus lenyap. Penggunaan kedua fakta lingkar itu membuat polinomial tersebut habis dibagi oleh suatu faktor tetap; pembagian menghasilkan polinomial tak nol berderajat lebih rendah dengan sifat yang sama, dan itu mustahil, karena kita sudah mengambil yang terendah.

Argumen tanda itu adalah perubahan utama Balko: argumen itu menggantikan argumen asli yang “melibatkan bentuk bilinear tak merosot dan komplemen ortogonal”. Ia juga membuktikan fakta lingkar itu dengan cara lain dan mengisolasi setiap titik secara lebih langsung.

Jaringan lain ikut terjawab sekaligus

Jawabannya tetap Z(n) jika yang dihitung, alih-alih persilangan, adalah pasangan kurva yang bersilangan sama sekali, atau yang bersilangan sebanyak bilangan ganjil kali — asalkan kurva-kurva yang berbagi titik tidak pernah bertemu di tempat lain. Digabungkan dengan reduksi-reduksi sebelumnya, teorema ini juga memberikan bilangan persilangan eksak untuk graf lengkap yang sebagian sambungannya dihapus, untuk salinan-salinan graf lengkap yang dirangkai sepanjang sebuah lintasan atau mengelilingi sebuah siklus genap, dan untuk sekeluarga jaringan mirip fraktal yang disebut graf Sierpiński yang diperluas.

Ambil satu kurva saja dari graf lengkap 6 titik, dan minimumnya turun dari 3 persilangan menjadi 2; pada 8 titik, dari 18 menjadi 15.