Lompatan Kecil ke Depan yang Sangat Besar dalam Teori Graf

Pada tanggal 15 Maret, pengumuman seminar yang menggelitik mengirimkan gemuruh melalui bidang kombinatorika, studi matematika tentang penghitungan. Tiga kolaborator berencana untuk memberikan khotbah yang terkoordinasi pada hari berikutnya. Julian Sahasrabudhe akan alamat ahli matematika di Cambridge, Inggris, sementara Simon Griffiths akan berbagi berita di Rio de Janeiro dan Marcelo Campos di Sao Paulo. Ketiga ceramah tersebut menggunakan judul yang identik dan abstrak dua kalimat yang samar yang merujuk pada "kemajuan terbaru pada masalah lama Erdős". Sedangkan Paul Erdős, seorang matematikawan Hongaria yang meninggal pada tahun 1996, berpose ratusan masalah selama karirnya, kombinator dengan cepat menebak masalah spesifik yang ingin dibicarakan oleh ketiganya. Desas-desus beredar tentang sesuatu yang disebut bilangan Ramsey, salah satu bilangan tersulit untuk dihitung dalam semua matematika.

Angka Ramsey telah melahirkan seluruh disiplin yang disebut teori Ramsey, yang mencari pola yang tak terhindarkan dalam sejumlah besar sistem.

Misalnya, Anda mencoba menyebarkan semua bilangan bulat di antara sejumlah keranjang, dan Anda ingin menghindari penempatan urutan angka dengan jarak yang sama di salah satu keranjang. Teori Ramsey menunjukkan bahwa Anda akan gagal (kecuali jika Anda memiliki ember yang sangat banyak). Teori ini dapat diterapkan pada hampir semua hal yang dapat Anda hitung. Pelajaran utamanya adalah bahwa "Anda tidak dapat membuat sistem yang benar-benar kacau," kata Benny Sudakov, ahli matematika di Swiss Federal Institute of Technology Zurich.

Angka Ramsey mengukur seberapa besar contoh paradigmatik harus sebelum pola tertentu muncul. Namun terlepas dari sentralitasnya, tidak ada yang bisa menghitung jumlah Ramsey untuk semua kecuali contoh paling sederhana. Hal terbaik yang dapat mereka lakukan adalah menemukan batasan (atau batasan) tentang apa yang mungkin terjadi. Bahkan saat itu, batas atas yang pertama kali didirikan oleh Erdős dan seorang kolaborator hampir seabad yang lalu hampir tidak bergerak.

Kemudian, dalam seminar tanggal 15 Maret, dan dalam makalah yang diposting malam itu, para peneliti mengumumkan bahwa mereka telah memperbaiki batas atas bilangan Ramsey dengan jumlah yang eksponensial.

"Saya terpana," kata Yuval Wigderson, seorang ahli matematika di Universitas Tel Aviv, mendengar tentang hasil baru. "Saya benar-benar gemetar selama setengah jam hingga satu jam."

Garis Partai

Teori Ramsey paling sering mengajukan pertanyaan baik tentang bilangan bulat atau tentang grafik. Sebuah grafik, dalam konteks ini, mengacu pada kumpulan titik yang disebut simpul, dihubungkan dengan garis yang disebut tepi, yang dapat memiliki sifat seperti panjang atau — seperti dalam kasus bilangan Ramsey — warna.

Grafik lengkap itu rumit dan sederhana — setiap node terhubung ke setiap node lainnya. Angka Ramsey menjelaskan berapa banyak simpul yang harus dimiliki oleh sebuah graf lengkap untuk dipaksa memiliki struktur tertentu. Katakanlah tepi grafik lengkap diberi salah satu dari dua warna: merah atau biru. Dan katakanlah Anda mencoba mewarnai tepi dengan cara yang menghindari menghubungkan sekelompok node dengan tepi dengan warna yang sama. Pada tahun 1930, Frank Ramsey membuktikan bahwa jika sebuah grafik cukup besar, menjadi tidak mungkin untuk menghindari pembuatan apa yang oleh matematikawan disebut klik monokromatik - sekelompok simpul yang ujung-ujungnya berwarna merah, atau biru.

Seberapa besar, tepatnya, grafik harus sebelum klik monokromatik terpaksa muncul? Jawabannya tergantung pada ukuran klik. Ramsey menunjukkan bahwa terdapat suatu bilangan, yang sekarang disebut bilangan Ramsey, yang mewakili jumlah minimum simpul yang harus ada klik monokromatik dengan ukuran tertentu, tidak peduli bagaimana ujung-ujungnya diwarnai.

Tapi ukuran nomor Ramsey sulit untuk dijabarkan. Pada tahun 1935, lima tahun setelah Ramsey menunjukkan keberadaannya, Erdős dan George Szekeres memberikan batas atas baru yang lebih ketat tentang seberapa besar bilangan Ramsey untuk klik dengan ukuran tertentu. Namun sejak saat itu, ahli matematika hampir tidak dapat meningkatkan perhitungan Erdős dan Szekeres.

Untuk mendapatkan intuisi yang lebih baik tentang artinya, pertimbangkan contoh klasik, di mana simpul mewakili tamu di sebuah pesta. Warnai tepi antara dua tamu merah jika mereka pernah bertemu sebelumnya, dan biru jika mereka belum pernah bertemu. Anda dapat memilih ukuran klik yang Anda suka — undang cukup banyak orang ke pesta, dan Anda tidak dapat menghindari mengundang sekelompok orang yang saling mengenal satu sama lain (sebuah klik dalam berbagai arti kata) atau mengundang sekelompok orang yang belum pernah bertemu sebelumnya.

“Hal paling sederhana yang dapat Anda miliki dalam grafik adalah klik monokromatik,” kata Maria Chudnovsky, seorang matematikawan di Princeton University. “Sungguh menakjubkan bahwa di setiap grafik besar Anda dapat menemukan yang besar. Sama sekali tidak jelas.”

Beberapa angka Ramsey pertama relatif sederhana untuk dihitung. Katakanlah Anda ingin mengetahui ukuran grafik terkecil yang mau tidak mau harus memiliki klik ukuran dua, atau R(2) untuk ahli matematika. Karena graf lengkap dengan dua simpul hanyalah dua simpul yang dihubungkan oleh sebuah sisi, dan sisi tersebut harus berwarna merah atau biru, R(2) adalah 2. Lebih umum, R(k), atau nomor Ramsey dari k, adalah jumlah minimum simpul yang tidak dapat dihindari oleh grafik yang mengandung klik ukuran k.

Tidak terlalu sulit untuk menunjukkan bahwa bilangan Ramsey untuk klik berukuran 3, atau R(3), adalah 6 (lihat grafik). Namun baru pada tahun 1955 R(4) ditetapkan menjadi 18. R(5) masih belum diketahui — setidaknya 43 dan tidak lebih besar dari 48. Meskipun angka ini kecil, memilah-milah semua warna yang mungkin tidak ada pertanyaan itu, kata David Conlon dari California Institute of Technology. Pertimbangkan jumlah pewarnaan pada grafik lengkap dengan 43 node. “Anda memiliki 903 sisi; masing-masing bisa diwarnai dengan dua cara,” jelasnya. “Jadi kamu dapat 2⁹⁰³, yang sangat besar secara astronomis.”

Saat ukuran klik bertambah, tugas untuk menentukan nomor Ramsey semakin sulit. Erdös menyindir bahwa perang habis-habisan dengan alien yang menuntut secara matematis akan lebih mudah daripada mencobanya cari tahu R(6), yaitu antara 102 dan 165. Kisaran ketidakpastian tumbuh dengan cepat: Menurut perkiraan yang disusun oleh Stanisław Radziszowski, R(10) bisa sekecil 798 dan sebesar 23,556. Tapi tujuan matematikawan jauh melampaui angka Ramsey 10. Mereka menginginkan rumus yang akan memberikan estimasi yang baik untuk R(k), bahkan — atau khususnya — kapan k sangat besar.

"Saya tidak tahu seseorang dalam kombinatorik yang tidak memikirkan masalah ini setidaknya sedikit," kata Wigderson. “Masalah ini, menurut saya, sangat istimewa.”

Perintah di Pengadilan

Frank Ramsey adalah sosok yang eklektik dan brilian yang meninggal saat berusia 26 tahun. Hanya beberapa minggu sebelum dia meninggal, the Prosiding Masyarakat Matematika London diterbitkan kertas di mana dia memperkenalkan nomor Ramsey. Pekerjaan itu bahkan bukan tentang grafik, tetapi tentang masalah dalam logika matematika. Ramsey membuktikan bahwa pernyataan yang memenuhi kondisi tertentu harus benar setidaknya untuk beberapa waktu. Salah satu syaratnya adalah ada "alam semesta" skenario yang besar untuk menguji pernyataan tersebut. Sebagai batu loncatan untuk hasil ini, Ramsey menunjukkan bahwa bilangan Ramsey terbatas.

Lima tahun kemudian, Erdős dan Szekeres menunjukkan jumlah Ramsey k kurang dari 4^k. Dan 12 tahun setelah itu, Erdős menunjukkan bahwa itu lebih besar dari sekitar $latex sqrt{2}^k$. Untuk melakukan itu, dia menghitung peluang sebuah grafik dengan tepi berwarna acak mengandung klik monokromatik. Teknik "probabilistik" ini menjadi sangat berpengaruh dalam teori graf. Itu juga menjebak R(k) antara dua tiang gawang yang tumbuh secara eksponensial: $latex sqrt{2}^k$ dan $latex 4^k$.

Seiring berlalunya dekade, banyak matematikawan berusaha mempersempit kesenjangan antara nilai yang mungkin dari bilangan Ramsey. Beberapa berhasil: Pada tahun 1975, Joel Spencer melipatgandakan batas bawah. Dan serangkaian makalah oleh Conlon, Andrew Thomason dan Ashwin Sahu terdorong ke bawah batas atas dengan faktor sekitar $latex 4^{log(k)^2}$ pada tahun 2020. Namun dibandingkan dengan ukuran batas pada nomor Ramsey, penyesuaian ini kecil. Sebaliknya, setiap pengurangan ke 4 dalam rumus Erdős dan Szekeres R(k) <4^k akan menjadi peningkatan eksponensial, tumbuh secepat k semakin besar.

“Sepertinya itu hanya pertanyaan kecil yang lucu,” kata Rob Morris, seorang matematikawan di IMPA, Institut Matematika Murni dan Terapan Brasil, di Rio de Janeiro, yang ikut menulis hasil baru bersama Campos, Griffiths, dan Sahasrabudhe. “Apresiasinya agak halus. Tetapi orang-orang sangat peduli tentang itu. Ini mungkin pernyataan yang meremehkan. “Seandainya mereka membuktikannya pada tahun 1936, orang akan berkata, Oke, jadi apa masalahnya?” kata Béla Bollobás, yang merupakan penasihat doktoral Morris dan Sahasrabudhe di University of Memphis. “Sejak itu, terbukti bahwa ini adalah masalah yang sangat besar, karena selama bertahun-tahun, beberapa ribu makalah telah ditulis tentang berbagai varian masalah Ramsey.” Sebagai Liana Yepremyan, seorang matematikawan di Universitas Emory, berkata, "Bilangan Ramsey menciptakan jembatan antara kombinatorik dan probabilitas dan geometri."

Teori permainan

 Pada Agustus 2018, Sahasrabudhe adalah postdoctoral fellow di bawah Morris di IMPA. Keduanya berharap untuk memulai proyek baru dengan Griffiths, yang mengajar di Universitas Katolik Kepausan terdekat makalah oleh Conlon menarik perhatian mereka. Makalah tersebut menguraikan kemungkinan strategi untuk mendapatkan peningkatan eksponensial pada bilangan Ramsey. Griffiths, Morris dan Sahasrabudhe mulai mempermainkan ide tersebut.

“Awalnya sangat mengasyikkan,” kenang Sahasrabudhe. Mereka hanya membutuhkan waktu sekitar satu bulan, katanya, untuk menyusun sketsa argumen mereka.

Rencana mereka adalah membangun ide yang digunakan dalam bukti asli Erdős dan Szekeres bahwa $lateks R(k) < 4^k$. Untuk membuktikan bahwa angka Ramsey adalah paling banyak $latex 4^k$, bayangkan bermain game pada grafik lengkap dengan node $latex 4^k$. Gim ini memiliki dua pemain. Pertama, lawan Anda mewarnai setiap sisi merah atau biru, berharap untuk mewarnai tepi dengan cara yang menghindari terciptanya klik monokromatik. k node.

Setelah lawan selesai mewarnai, tugas Anda adalah mencari klik monokromatik. Jika Anda menemukannya, Anda menang.

Untuk memenangkan permainan ini, Anda dapat mengikuti strategi sederhana. Ini membantu untuk berpikir (secara metaforis) tentang menyortir node Anda menjadi dua ember. Simpul dalam satu ember akan membentuk klik biru, dan simpul lainnya akan membentuk klik merah. Beberapa node akan dihapus, tidak pernah terdengar lagi. Pada awalnya, kedua keranjang kosong, dan setiap simpul merupakan kandidat untuk masuk ke salah satunya.

Mulailah dengan node mana pun yang sesuai dengan keinginan Anda. Kemudian lihat ujung penghubungnya. Jika setengah atau lebih tepinya berwarna merah, hapus semua tepi biru dan node yang terhubung dengannya. Kemudian masukkan pilihan awal Anda ke dalam ember "merah". Semua tepi merah simpul ini masih hidup dan sehat, menempel pada grafik lainnya dari dalam ember. Jika lebih dari separuh tepinya berwarna biru, Anda secara analog menghapus tepi dan simpul merah, dan memasukkannya ke dalam ember biru.

Ulangi sampai Anda tidak memiliki node yang tersisa. (Karena grafik selesai, setiap node yang tersisa di titik mana pun terhubung ke kedua bucket hingga ditempatkan di salah satunya.)

Setelah selesai, lihat ke dalam ember. Karena node masuk ke ember merah hanya setelah tetangga birunya dihilangkan, semua node di ember merah dihubungkan oleh tepi merah - mereka membentuk klik merah. Demikian pula, ember biru membentuk klik biru. Jika grafik asli Anda memiliki setidaknya simpul $latex 4^k$, dapat dibuktikan bahwa salah satu keranjang ini harus berisi setidaknya k node, menjamin klik monokromatik pada grafik aslinya.

Argumen ini cerdas dan elegan, tetapi membuat Anda membangun dua klik — satu biru dan satu merah — meskipun Anda hanya benar-benar membutuhkan satu. Akan lebih efisien untuk selalu menjadi merah, jelas Conlon. Di bawah strategi ini, Anda akan memilih simpul di setiap langkah, menghapus tepi birunya, dan membuangnya ke ember merah. Ember merah kemudian akan terisi dengan cepat, dan Anda akan mengumpulkan klik merah k node di separuh waktu.

Tetapi strategi Anda harus berhasil untuk pewarnaan merah-biru apa pun, dan sulit untuk mengetahui apakah Anda selalu dapat menemukan simpul dengan banyak tepi merah. Jadi mengikuti saran Conlon berisiko menabrak simpul yang hampir tidak memiliki tepi merah yang melekat padanya. Itu akan memaksa Anda untuk menghapus sebagian besar grafik sekaligus, membuat Anda berebut untuk membangun klik Anda sebelum Anda kehabisan node. Untuk melaksanakan saran Conlon, Griffiths, Morris, dan Sahasrabudhe perlu membuktikan bahwa risiko ini dapat dihindari.

Ujian Buku Terbuka

Dalam memperbarui gameplay mereka, Griffiths, Morris, dan Sahasrabudhe mengikuti rute yang sedikit lebih memutar. Alih-alih membangun klik monokromatik secara langsung dengan melemparkan simpul ke dalam ember merah dan biru mereka, pertama-tama mereka berfokus pada pembangunan struktur yang disebut buku merah.

Sebuah buku, dalam teori graf, terdiri dari dua bagian: Ada klik monokromatik, yang disebut "tulang belakang", dan kelompok simpul kedua yang berbeda yang disebut "halaman". Dalam buku merah, semua tepi yang menghubungkan simpul di dalam tulang belakang berwarna merah, begitu pula tepi yang menghubungkan tulang belakang ke halaman. Namun, tepi yang menghubungkan node di dalam halaman dapat berupa kombinasi warna apa pun. Conlon telah mencatat dalam makalahnya tahun 2018 bahwa jika Anda dapat menemukan klik merah di dalam halaman buku, maka Anda dapat menggabungkannya dengan tulang belakang untuk mendapatkan klik merah yang lebih besar. Ini memungkinkan Anda menguraikan pencarian untuk klik merah besar menjadi dua pencarian yang lebih mudah. Pertama, cari buku merah. Kemudian cari klik di halaman buku.

Griffiths, Morris, dan Sahasrabudhe ingin menyesuaikan algoritme pemenang permainan sehingga membuat buku merah, bukan klik merah. Meskipun mereka menyelesaikan rencana ini hanya beberapa minggu setelah proyek mereka, butuh waktu bertahun-tahun untuk membuatnya bekerja. Mereka masih perlu mencegah ancaman kehilangan semua sisi merah mereka.

“Kami terjebak untuk waktu yang sangat lama,” kata Campos, yang bergabung dengan proyek tersebut pada tahun 2021.

Januari ini, keempat ahli matematika itu setuju untuk beralih ke versi lain dari soal tersebut. Versi itu terdengar lebih rumit, tetapi ternyata lebih mudah.

Selama ini, tim telah fokus pada nomor Ramsey R (k), juga dikenal sebagai bilangan Ramsey "diagonal". Grafik berukuran R(k) harus berisi k node, semuanya terhubung dengan tepi dengan warna yang sama, tetapi tidak masalah apakah warna itu merah atau biru. Di sisi lain, nomor Ramsey "off-diagonal" R (k, l) mengukur seberapa besar grafik harus sebelum berisi salah satu klik merah dengan k node, atau klik biru dengan l node. Alih-alih terus memecahkan masalah diagonal, kelompok tersebut memutuskan untuk mencoba versi off-diagonal. Ini terbukti wahyu.

“Untuk waktu yang lama, rasanya seperti setiap pintu yang Anda dorong tertutup, atau setidaknya cukup sulit untuk dilewati,” kata Griffiths. “Dan setelah perubahan itu, Anda merasa seperti setiap pintu terbuka. Entah bagaimana, semuanya tampak berhasil. Dalam versi off-diagonal, mereka menemukan cara untuk menghapus sekumpulan tepi biru sekaligus mengikuti protokol tertentu, yang meningkatkan kerapatan tepi merah, dan menyebabkan peningkatan batas pada bilangan Ramsey off-diagonal. Metode ini, yang disebut argumen "peningkatan kepadatan", sebelumnya telah digunakan untuk menyelesaikannya masalah penting lainnya dalam kombinatorik, tetapi belum digunakan pada masalah nomor Ramsey.

Keempat matematikawan itu kemudian menggunakan batas baru pada bilangan Ramsey di luar diagonal untuk membuka jalan bagi hasil diagonal. Pada awal Februari, mereka akhirnya menurunkan batas bilangan Ramsey dengan faktor eksponensial, pencapaian yang dicari para matematikawan selama hampir seabad. Dan mereka melakukannya dengan memodernisasi garis argumen yang sama yang dikemukakan oleh Erdős dan Szekeres pada tahun 1935.

Epsilon, Epsilon

Setelah pembicaraan pada 16 Maret, para hadirin mulai mengkonfirmasi rumor tersebut. Foto-foto ceramah Sahasrabudhe beredar melalui panggilan telepon dan pesan pribadi—bahkan di a posting yang tidak jelas tapi sugestif di blog matematikawan Gil Kalai. Campos, Griffiths, Sahasrabudhe dan Morris mengklaim telah menunjukkan bahwa $latex R(k) < 3.993^k$. Malam itu, empat penulis memposting makalah mereka secara online, memungkinkan ahli matematika untuk melihat bukti baru untuk diri mereka sendiri.

“Saya pikir banyak dari kita pada dasarnya tidak berharap untuk melihat peningkatan seperti itu dalam hidup kita,” kata Matija Bucić, seorang matematikawan di Princeton University dan Institute for Advanced Study. "Saya pikir ini adalah hasil yang benar-benar luar biasa."

Banyak ahli berharap bahwa, dengan penghalang eksponensial ditebang, lebih banyak kemajuan akan segera menyusul. Para penulis makalah baru sengaja tidak memaksakan metode mereka sampai batasnya, untuk menghindari mengaburkan argumen mereka dengan rincian yang tidak perlu. “Saya sangat tertarik dengan seberapa jauh metode ini bisa berjalan, karena saya tidak tahu,” kata Campos.

“Ini adalah bukti yang sangat cerdik, benar-benar luar biasa, dan terobosan yang tulus. Jadi sekarang saya berharap pintu air dibuka,” kata Bollobás. “Saya yakin dalam waktu tiga tahun, perdebatannya adalah tentang kemungkinan perbaikan. Bisakah kita meningkatkan 3.993 menjadi 3.9? Mungkin ke 3.4? Dan bagaimana dengan 3?”

Bukti baru masuk pada 56 halaman, dan akan memakan waktu berminggu-minggu untuk setiap detail diverifikasi sepenuhnya oleh komunitas kombinatorik. Tapi rekan-rekan optimis. “Kelompok penulis ini, mereka adalah orang-orang yang sangat serius. Dan mereka adalah orang-orang yang sangat, sangat ahli dalam hal-hal yang sangat teknis,” kata Wigderson.

Mengenai kolaboratornya, Griffiths setuju. “Merupakan hak istimewa untuk bekerja dengan orang-orang brilian, bukan? Dan saya pikir itulah yang saya sangat syukuri,” katanya. "Jika mereka menyerahkannya kepadaku, aku mungkin membutuhkan waktu lima tahun lagi untuk mendapatkan detailnya dengan benar."