Tampilan Close-Up Mengungkapkan Titik 'Lebur' dari Grafik Tak Terbatas | Majalah Kuanta

Pada tahun 2008, ahli matematika Oded Schramm meninggal dalam kecelakaan pendakian di pegunungan Cascade sekitar 50 mil sebelah timur Seattle. Meskipun dia baru berusia 46 tahun, dia telah membangun bidang matematika yang benar-benar baru.

“Dia adalah ahli matematika yang luar biasa,” kata Itai Benyamini, seorang ahli matematika di Institut Sains Weizmann dan teman serta kolaborator Schramm. “Sangat kreatif, sangat elegan, sangat orisinal.”

Pertanyaan-pertanyaan yang dia ajukan masih mendorong batas-batas teori probabilitas dan fisika statistik. Banyak dari pertanyaan-pertanyaan ini berkaitan dengan struktur matematika yang memiliki transisi fase – perubahan makroskopis yang tiba-tiba, seperti pencairan es menjadi air. Sama seperti bahan yang berbeda memiliki titik leleh yang berbeda, transisi fase struktur matematika juga bervariasi.

Schramm menduga bahwa transisi fase dalam proses yang disebut perkolasi dapat diperkirakan hanya dengan menggunakan tampilan sistem dari dekat - yang disebut perspektif lokal - untuk banyak struktur matematika penting. Memperbesar dan melihat keseluruhannya tidak akan mengubah perhitungan secara signifikan. Dalam 15 tahun terakhir, para ahli matematika telah memotong sebagian kecil dari dugaan tersebut, namun hingga saat ini, mereka belum mampu menyelesaikannya sepenuhnya.

Di sebuah pracetak diposting pada bulan Oktober, Tom Hutchcroft dari California Institute of Technology dan mahasiswa doktoralnya Philip Easo membuktikan dugaan lokalitas Schramm. Pembuktian mereka bergantung pada ide-ide besar dari berbagai teori probabilitas dan bidang matematika lainnya, yang mereka gabungkan dengan cara yang cerdas.

“Ini adalah makalah yang luar biasa. Ini akumulasi kerja panjang,” kata Benjamini.

Cluster Tak Terbatas

Kata “perkolasi” awalnya mengacu pada pergerakan fluida melalui media berpori, seperti air yang mengalir melalui bubuk kopi atau minyak yang merembes melalui celah-celah batu.

Pada tahun 1957, ahli matematika Simon Ralph Broadbent dan John Michael Hammersley mengembangkan model matematika dari proses fisik ini. Dalam beberapa dekade setelahnya, model ini telah menjadi objek studi tersendiri. Para ahli matematika mempelajari perkolasi karena hal ini menghasilkan keseimbangan yang penting: Pengaturannya sederhana, namun memperlihatkan fitur yang rumit dan membingungkan.

“Ini semacam model kanonik bagi ahli matematika,” kata Hutchcroft. “Anda dapat memikirkan berbagai hal secara visual. Itu membuatnya sangat menyenangkan untuk diajak bekerja sama.”

Perkolasi dimulai dengan suatu graf, yaitu himpunan titik-titik (titik) yang dapat dihubungkan oleh sisi-sisinya (garis). Salah satu contoh paling sederhana adalah kotak persegi, dengan simpul-simpul yang berjajar membentuk sudut-sudut persegi dan tepi-tepi yang menghubungkan beberapa di antaranya.

Sesaat sebelum kematiannya, Schramm menduga bahwa teorema Grimmett dan Marstrand dapat digeneralisasikan. Dia berpendapat bahwa ambang batas perkolasi ditentukan sepenuhnya oleh perspektif close-up, atau “mikroskopis”, untuk kelas besar grafik yang dikenal sebagai grafik transitif.

Pada tahun 2009, Benyamin, Asaf Nachmias dan Yuval Peres terbukti Dugaan lokalitas Schramm, seperti yang sekarang diketahui, untuk tipe graf transitif tertentu yang menyerupai pohon. Schramm, bagaimanapun, telah mendalilkan bahwa hal ini berlaku untuk semua grafik transitif (dengan pengecualian untuk grafik satu dimensi).

Dalam graf transitif, semua simpul terlihat serupa. Grid dua dimensi adalah salah satu contohnya. Jika Anda memilih dua simpul mana pun, Anda selalu dapat menemukan simetri yang memindahkan satu simpul ke simpul lainnya.

Hubungan ini berlaku untuk semua graf transitif. Karena kesimetrian ini, jika Anda memperbesar dan melihat dua bagian grafik transitif yang berukuran sama, keduanya akan terlihat sama. Karena alasan ini, Schramm percaya bahwa perspektif close-up cukup untuk memungkinkan ahli matematika menghitung ambang batas perkolasi untuk semua grafik transitif.

Grafik transitif dapat memiliki banyak bentuk dan bentuk. Bentuknya bisa berupa kisi-kisi sederhana, terdiri dari kotak, segitiga, segi enam, atau bentuk lainnya. Atau mereka dapat membentuk objek yang lebih kompleks, seperti “pohon 3-beraturan,” di mana satu titik pusat terhubung ke tiga simpul, dan masing-masing simpul kemudian bercabang untuk membuat dua simpul baru ad infinitum, beberapa langkah pertama dapat dilihat di sini:

Beragamnya grafik transitif berkontribusi pada sulitnya membuktikan dugaan lokalitas Schramm. Dalam kurun waktu 15 tahun antara dugaan Schramm dan bukti Easo dan Hutchcroft, berbagai kelompok matematikawan membuktikan dugaan tersebut untuk jenis grafik tertentu, namun gagasan mereka tidak pernah meluas ke kasus umum.

“Ruang dari semua kemungkinan geometri sangatlah luas, dan selalu ada hal-hal aneh yang mengintai,” kata Hutchcroft.

Melebarkan Lensa

Easo dan Hutchcroft pada awalnya tidak mencari solusi untuk dugaan lokalitas Schramm, yang berlaku untuk grafik tak hingga. Mereka malah mempelajari perkolasi pada grafik berhingga. Namun mereka memiliki ide yang tiba-tiba mengalihkan perhatian mereka ke dugaan tersebut.

“Kami menemukan alat baru ini, dan kami berpikir, oh, alat ini sepertinya berguna untuk menyerang lokalitas,” kata Easo.

Untuk membuktikan dugaan tersebut, mereka perlu menunjukkan bahwa perspektif mikroskopis memberikan gambaran akurat tentang ambang batas perkolasi. Saat Anda melihat hanya sebagian dari grafik dan mengamati cluster besar yang terhubung, Anda mungkin berasumsi bahwa grafik tersebut memiliki cluster yang tak terbatas dan oleh karena itu berada di atas ambang batas perkolasi. Easo dan Hutchcroft berusaha membuktikannya.

Mereka mengandalkan teknik yang dapat dianggap sebagai “pelebaran lensa.” Mulai dari satu titik. Kemudian perkecil untuk melihat semua simpul yang hanya berjarak satu sisi pada grafik asli. Pada kotak persegi, Anda sekarang dapat melihat total lima simpul. Perluas lensa lagi untuk melihat semua simpul dalam jarak dua sisi, lalu jarak tiga sisi, empat sisi, dan seterusnya.

Easo dan Hutchcroft mengatur dial yang menentukan berapa banyak link yang ada di dekat tempat mereka melihat cluster besar. Mereka kemudian melebarkan lensanya, mengamati semakin banyak tepian yang berkumpul dalam kelompok besarnya. Saat mereka melakukannya, mereka harus meningkatkan kemungkinan adanya tautan, yang membuatnya lebih mudah untuk menunjukkan bahwa grafik tersebut memiliki komponen terhubung yang besar. Ini adalah tindakan penyeimbangan yang rumit. Mereka perlu memperluas bidang pandang dengan cukup cepat dan menambahkan tautan dengan cukup lambat untuk menampilkan grafik tak terhingga secara penuh tanpa mengubah posisi dial secara drastis.

Mereka mampu menunjukkan bahwa klaster yang besar tumbuh lebih cepat dibandingkan klaster yang lebih kecil, sehingga, seperti yang dikatakan Easo, “klaster Anda bertumbuh semakin cepat seiring dengan semakin besarnya, seperti saat Anda menggelindingkan bola salju.”

Untuk grid persegi, jumlah titik tumbuh relatif lambat. Ini kira-kira sama dengan lebar kuadrat lensa Anda. Setelah 10 langkah, Anda akan menemukan sekitar 100 simpul. Namun pohon 3 biasa tumbuh lebih cepat secara eksponensial — kira-kira 2 pangkat dari lebar lensa Anda. Setelah 10 langkah, Anda akan melihat sekitar 1,024 simpul. Ilustrasi di bawah menunjukkan bagaimana pohon 3 beraturan menjadi jauh lebih besar setelah hanya tujuh langkah, meskipun kotak persegi memiliki lebih banyak simpul pada awalnya. Secara umum, grafik dapat memiliki tingkat pertumbuhan yang berbeda-beda pada skala yang berbeda — grafik mungkin dimulai dengan cepat, lalu melambat.

Kembali pada tahun 2018, Hutchcroft menggunakan ide serupa untuk membuktikan dugaan lokalitas untuk graf yang tumbuh cepat seperti pohon beraturan 3. Namun cara ini tidak berhasil untuk grafik dengan pertumbuhan lambat seperti kotak persegi, atau untuk grafik yang tumbuh dengan kecepatan sedang, sehingga tidak memenuhi kriteria matematis untuk pertumbuhan cepat maupun kriteria pertumbuhan lambat.

“Di sinilah keadaan menjadi sangat membuat frustrasi selama tiga tahun,” kata Hutchcroft.

Struktur versus Ekspansi

Untuk grafik yang menggabungkan tingkat pertumbuhan pada skala berbeda, Anda harus menggunakan berbagai teknik.

Salah satu fakta yang sangat membantu adalah, seperti yang dijelaskan Easo, “jika grafik terlihat tumbuh lambat pada skala tertentu, maka grafik tersebut akan macet.” Ini akan terus tumbuh secara perlahan pada skala yang lebih besar. Karena grafik dengan pertumbuhan lambat memiliki struktur tambahan yang ditentukan oleh cabang matematika yang disebut teori grup, diketahui juga bahwa jika Anda memperkecil tampilannya cukup jauh, grafik dengan pertumbuhan lambat akan menampilkan geometri yang secara matematis jinak.

Pada tahun 2021, Sébastien Martineau dari Universitas Sorbonne di Paris, bekerja dengan Daniel Contreras dan Vincent Tassion dari ETH Zurich, dapat menggunakan properti ini untuk membuktikan dugaan lokalitas Schramm untuk grafik yang akhirnya tumbuh perlahan.

Pada titik ini, kedua kelompok ahli matematika telah berhasil mengatasi dugaan tersebut dari arah yang berbeda: pertumbuhan cepat dan pertumbuhan lambat. Namun hal ini menyisakan kesenjangan yang cukup besar. Pertama, ada kategori pertumbuhan menengah yang tidak tercakup dalam teknik Easo dan Hutchcroft atau berdasarkan bukti Contreras, Martineau, dan Tassion. Masalah lainnya adalah argumen tersebut masih tidak berlaku pada grafik dengan tingkat pertumbuhan yang berubah-ubah – hanya grafik yang tetap cepat atau lambat. Agar argumen Contreras, Martineau, dan Tassion dapat diterapkan pada grafik arbitrer, geometri pada akhirnya akan terlihat jinak ketika Anda memperkecilnya, tidak cukup, Easo menjelaskan: “Kami membutuhkannya agar terlihat jinak sekarang, mendekati skala saat ini.”

Antah Berantah

Grafik transitif pertumbuhan menengah sangatlah misterius. Matematikawan belum pernah menemukan contoh grafik transitif yang pertumbuhannya berada pada kisaran ini. Mungkin saja mereka tidak ada. Namun para ahli matematika belum membuktikan bahwa mereka tidak ada, jadi bukti lengkap dugaan lokalitas Schramm harus menjawabnya. Tantangan lainnya adalah Easo dan Hutchcroft perlu mengatasi grafik yang mungkin hanya memiliki pertumbuhan menengah sebentar pada skala panjang tertentu, meskipun grafik tersebut tumbuh lebih cepat atau lebih lambat saat Anda memperbesar atau memperkecil.

Easo dan Hutchcroft menghabiskan sebagian besar waktu setahun terakhir untuk memperluas hasil mereka agar dapat diterapkan pada grafik yang tidak tercakup dalam metode sebelumnya.

Pertama, mereka memodifikasi teknik tahun 2018 yang diterapkan Hutchcroft pada grafik yang tumbuh cepat untuk bekerja pada grafik yang mengubah tingkat pertumbuhan pada skala yang berbeda. Mereka kemudian menangani kasus pertumbuhan yang lambat, di makalah setebal 27 halaman mereka berbagi pada bulan Agustus bahwa mereka memperluas pekerjaan di Contreras, Martineau, dan Tassion. Terakhir, dalam pracetak bulan Oktober, mereka menyusun argumen lain dengan menggunakan teori jalan acak — garis yang bergerak secara acak di ruang angkasa — untuk menangani kasus pertumbuhan menengah. Setelah trikotomi selesai, mereka telah membuktikan dugaan lokalitas Schramm.

“Kami harus mengerahkan semua yang kami ketahui untuk mengatasi masalah ini,” kata Hutchcroft.

Solusi ini memberikan wawasan yang lebih baik kepada ahli matematika tentang apa yang terjadi di atas ambang batas perkolasi, yang peluang terjadinya cluster tak terbatas adalah 100%, dan di bawahnya, yang peluangnya adalah 0%. Namun para ahli matematika masih bingung dengan apa yang terjadi tepat pada ambang batas sebagian besar grafik, termasuk kisi tiga dimensi. “Ini mungkin pertanyaan terbuka yang paling terkenal dan paling mendasar dalam teori perkolasi,” katanya Russel Lyons dari Universitas Indiana.

Grid dua dimensi adalah salah satu dari sedikit kasus di mana ahli matematika telah membuktikan apa yang terjadi tepat pada ambang batas: cluster tak terbatas tidak terbentuk. Dan setelah Grimmett dan Marstrand membuktikan versi dugaan lokalitas untuk lempengan besar, Grimmett dan kolaboratornya menunjukkan bahwa jika Anda memotong kotak 3D menjadi dua secara horizontal, menciptakan lantai, dan menyetel putaran tepat ke ambang perkolasi, tidak akan ada cluster tak terbatas yang muncul. Hasilnya menunjukkan bahwa grid tiga dimensi penuh, seperti halnya jaringan dua dimensi, mungkin tidak memiliki cluster tak terbatas pada ambang perkolasi.

Pada tahun 1996, Benjamini dan Schramm dugaan bahwa peluang untuk menemukan cluster tak terbatas tepat di ambang batas adalah nol untuk semua grafik transitif — seperti halnya untuk grid 2D atau grid 3D yang dibelah dua. Kini setelah dugaan mengenai lokalitas telah diselesaikan, pemahaman tentang apa yang terjadi tepat pada titik transisi mungkin akan semakin dekat.

Koreksi: Desember 18, 2023
Jumlah node dalam n link dari node awal pada 3 graf beraturan bertambah sekitar 2ⁿ, bukan 3ⁿ seperti yang dinyatakan dalam artikel ini pada awalnya. Artikel telah diperbaiki.

Quanta sedang melakukan serangkaian survei untuk melayani audiens kami dengan lebih baik. Ambil milik kami survei pembaca matematika dan anda akan diikut sertakan untuk menang secara gratis Quanta barang dagangan