Matematikawan Temukan Cara Baru Memprediksi Struktur Grafik | Majalah Quanta

Ini merupakan tahun yang menggembirakan dalam penelitian kombinatorik. Di awal tahun 2023, ahli matematika tercengang ketika dua dari itu masalah terbesar di lapangan diselesaikan dalam beberapa bulan. Sekarang, pertanyaan besar ketiga telah jatuh dengan bukti 14 halaman "yang benar-benar memiliki semua ide yang benar," kata Mehtaab Sawhney dari Massachusetts Institute of Technology, yang menambahkan: "Ini benar-benar mengejutkan."

Pertanyaan itu berkaitan dengan apa yang disebut bilangan Ramsey — besaran fundamental yang mencerminkan batas kemungkinan ketidakteraturan. Angka-angka ini mengukur ukuran yang dapat dicapai oleh kumpulan simpul dan sisi, yang disebut grafik, sebelum akhirnya memunculkan pola dan struktur.

Matematikawan telah mempelajari bilangan Ramsey, yang terkenal sulit dijabarkan, selama hampir satu abad. Dengan melakukan itu, mereka telah mengembangkan teknik yang telah menghasilkan kemajuan dalam berbagai disiplin ilmu di luar teori graf, termasuk teori bilangan dan kriptografi.

Tapi bukti baru, diposting online awal bulan ini, menandai keberangkatan dari teknik tersebut. Ini tidak hanya memecahkan masalah yang telah menolak kemajuan selama lebih dari 40 tahun, tetapi juga menyajikan peta jalan baru tentang bagaimana ahli matematika dapat menangani masalah Ramsey ke depannya.

Perencanaan Pesta Memenuhi Teori Graf

Untuk memahami apa itu nomor Ramsey, bayangkan Anda mengadakan pesta.

Berapa banyak orang yang perlu Anda undang untuk menjamin bahwa akan ada sekelompok orang yang saling mengenal satu sama lain, atau kelompok yang semuanya asing? Anda dapat menyandikan pertanyaan ini dalam bahasa grafik. Tetapkan simpul untuk setiap orang. Untuk n orang, Anda mengerti n sudut. Hubungkan setiap pasang simpul dengan sebuah sisi. Warnai tepinya merah jika orang yang bersangkutan saling mengenal, dan biru jika mereka orang asing.

Sekelompok kenalan atau orang asing diwakili oleh struktur yang disebut klik: sekumpulan simpul yang dihubungkan oleh sisi-sisi dengan warna yang sama. Nomor Ramsey r(s, t) adalah jumlah minimum orang yang harus Anda undang agar grup tidak dapat dihindari s kenalan atau t orang asing - dalam bahasa teori grafik, ukuran klik merah s atau ukuran klik biru t.

Misalnya, kita tahu itu r(4, 5) = 25. Jadi, Anda dapat mengadakan pesta dengan 24 orang, beberapa di antaranya saling mengenal, tanpa menyertakan grup yang terdiri dari empat kenalan bersama atau lima orang asing. Tetapi tambahkan satu orang lagi, dan Anda tidak dapat menghindari membuat setidaknya satu dari struktur ini.

Salah satu terobosan awal tahun ini dalam kombinatorik memberikan batas atas yang lebih ketat untuk bilangan Ramsey yang "simetris", di mana klik merah dan biru memiliki ukuran yang sama. Dengan angka Ramsey asimetris - subjek dari hasil baru - matematikawan memperbaiki ukuran klik merah dan bertanya apa yang terjadi jika ukuran klik biru menjadi besar secara acak.

Matematikawan hanya mampu menghitung dengan tepat segelintir bilangan Ramsey terkecil. Mereka membuktikan itu r(4, 5) = 25 pada tahun 1995. Tapi tidak ada yang tahu nilainya r(4, 6). Demikian pula, pada awal 1980-an, mereka menunjukkan bahwa r(3, 9) = 36, tetapi r(3, 10) tetap menjadi masalah terbuka. (Kasus simetris sama sulitnya: r(4) = 18, tetapi nilai dari r(5) tidak diketahui.)

Jadi, matematikawan malah mencoba memperkirakan angka Ramsey — menghasilkan batas atas dan bawah pada nilainya.

Pada 1990-an, mereka menggunakan teknik untuk menghasilkan grafik secara acak untuk membuktikan bahwa jika klik merah ditetapkan pada 3, dan klik biru menjadi semakin besar, ukuran bilangan Ramsey tumbuh sebagai kuadrat dari ukuran klik biru. Dengan kata lain, r(3, t) adalah sekitar t².

Bukti baru bertanya apa yang terjadi ketika ukuran klik merah ditetapkan pada 4, bukan 3. Pada tahun 1930-an, ditetapkan bahwa r(4, t) tumbuh tidak lebih cepat dari sekitar t³. Tapi batas bawah terbaik, yang ditemukan pada tahun 1970-an, adalah tentang t^5/2 - jauh lebih kecil.

Upaya untuk menutup celah dengan menaikkan batas bawah atau menurunkan batas atas gagal selama beberapa dekade, sampai sepasang ahli matematika menambahkan bahan utama.

Tersembunyi di Pandangan Biasa

Dalam 2019, Sam Matius, kemudian seorang mahasiswa pascasarjana di Free University of Brussels (VUB) sedang mencari inspirasi. Keahliannya adalah geometri terbatas, studi tentang pengaturan titik, garis, dan struktur lain dalam ruang yang ditentukan secara khusus. Tetapi meskipun menurutnya pekerjaan itu menarik, dia merasa terkekang oleh betapa ketat dan tepatnya konstruksi geometris ini.

Kemudian dia melihat kertas oleh dua matematikawan, Dhruv Mubayi dari University of Illinois, Chicago dan Jacques Verstraete dari Universitas California, San Diego. Mereka memikirkan kembali cara mendekati masalah Ramsey. Sementara teknik tradisional melibatkan pembuatan grafik secara acak untuk mendapatkan estimasi angka Ramsey yang baik, Mubayi dan Verstraete memulai dengan konstruksi “pseudorandom” yang terlihat acak, padahal sebenarnya tidak.

Sesuatu diklik di Mattheus. Mungkin, pikirnya, perspektif geometrisnya bisa membantu. Selama beberapa tahun berikutnya, ketika dia menyelesaikan pekerjaan pascasarjananya, dia menyimpan ide ini di benaknya. Dia kemudian melamar beasiswa Fulbright, yang akan memungkinkan dia untuk mengejar pascadoktoral dengan Verstraete di AS

Pada tahun 2022, tak lama setelah Mattheus dianugerahi Fulbright (bersama dengan persekutuan lain), dia pindah ke UCSD dan mulai bekerja dengan Verstraete r(4,t). Para matematikawan ingin menaikkan batas bawah untuk memenuhi batas atas yang diketahui. Untuk melakukan itu, mereka harus menemukan grafik dengan hampir t³ simpul yang tidak memiliki klik merah berukuran 4 atau klik biru berukuran t.

Agar bukti mereka berhasil, mereka merumuskan kembali masalahnya. Bayangkan hanya menghapus setiap tepi biru. Tujuannya sekarang menjadi untuk menemukan grafik tanpa klik merah ukuran 4, dan tidak ada kumpulan ukuran independen t (yaitu, set t simpul tanpa sisi).

Karya Mubayi dan Verstraete tahun 2019 menyiratkan bahwa jika Anda dapat membuat grafik pseudorandom tanpa klik merah ukuran 4, maka Anda dapat mengambil potongan acak untuk mendapatkan grafik yang lebih kecil tanpa kumpulan independen yang besar. Inilah tepatnya yang ingin ditemukan oleh Mattheus dan Verstraete. Dengan memulai dengan grafik yang lebih besar, mereka berharap menemukan grafik dengan hampir t³ simpul yang memenuhi kriterianya. “Di dalam grafik ini sembunyikan grafik Ramsey yang lebih baik,” kata Verstraete.

Masalahnya adalah menemukan konstruksi pseudorandom yang tepat untuk memulai.

Para ahli matematika harus sampai di sana dengan cara yang agak memutar. Mereka tidak memulai dengan grafik acak semu. Mereka tidak memulai dengan grafik sama sekali.

Alih-alih, Mattheus mengingat objek aneh yang disebut unital Hermitian, sesuatu yang cenderung sangat akrab dengan ahli geometri terbatas - tetapi ahli matematika yang bekerja di bidang kombinatorik sepertinya tidak akan pernah menemukannya.

Unital Hermitian adalah kumpulan titik khusus pada kurva, bersama dengan garis yang melewati titik tersebut dalam konfigurasi tertentu. Yang terpenting, itu juga dapat direpresentasikan sebagai grafik yang terdiri dari banyak klik besar tetapi hampir tidak tumpang tindih.

Grafik ini terkenal, dan banyak sifat-sifatnya telah dipelajari. Tapi itu tidak pernah dipertimbangkan dalam konteks masalah Ramsey. “Ini sangat spesifik untuk bisnis finite-geometry ini,” kata Mattheus.

Sekilas grafik mungkin tampak tidak berguna, karena memuat begitu banyak klik besar. Tetapi fitur kunci dari unital Hermitian adalah bahwa ia hanya berisi klik ukuran-4 yang simpulnya dikelompokkan bersama dengan cara yang tidak biasa. Karena sifat ini, relatif mudah bagi matematikawan untuk menghancurkan klik yang tidak diinginkan tersebut dengan menghapus sisi secara acak.

Penghapusan ini memberi mereka grafik baru tanpa klik ukuran 4 - tetapi masih berisi kumpulan independen yang besar. Mattheus dan Verstraete sekarang perlu membuktikan bahwa grafik ini acak semu. Dengan demikian, mereka akhirnya dapat menggunakan bukti 2019 seperti yang mereka harapkan. Mereka mengambil subgraf acak dengan tentang t³ simpul, dan dapat menjamin bahwa subgraf tersebut bebas dari kumpulan ukuran yang independen t.

Ini melengkapi buktinya. “Konstruksi ini benar-benar indah,” kata Sawhney.

Karya tersebut menandai perubahan dalam cara berpikir matematikawan tentang masalah Ramsey. "Sangat, sangat alami untuk mencoba menggunakan keacakan untuk mencoba mendorong sesuatu dan mendapatkan ikatan sebaik yang Anda bisa," kata David Conlon dari Institut Teknologi California. "Tapi apa yang sebenarnya ditunjukkan ini adalah bahwa keacakan hanya membuat Anda sejauh ini."