Get best of the week

Bukti pelangi menunjukkan keberadaan komponen standar dalam grafik

Matematikawan telah membuktikan bahwa salinan grafik yang lebih kecil selalu dapat secara ideal mencakup grafik yang lebih besar.



Pada 8 Januari, tiga ahli matematika menerbitkan bukti teorema dari kombinatorik yang dirumuskan hampir 60 tahun yang lalu, yang dikenal sebagai hipotesis Ringel. Secara kasar, ia memperkirakan bahwa grafik - konstruksi yang terdiri dari titik dan garis - dapat secara ideal dilipat dari potongan identik dengan ukuran yang lebih kecil.

Matematikawan dengan antusias menerima konfirmasi hipotesis ini.

"Nasib baik adalah bahwa karya ini memecahkan hipotesis yang sangat lama yang tidak dapat diverifikasi dengan metode lain," kata Gil Kalai , seorang ahli matematika di Universitas Ibrani di Yerusalem, yang tidak terkait dengan pekerjaan ini.

Hipotesis Ringel memprediksi bahwa tipe khusus dari grafik kompleks - dengan trilyunan simpul dan tepian - dapat "ubin", mis. sepenuhnya menutupi, dengan salinan terpisah dari grafik yang lebih kecil dari jenis tertentu. Dari sudut pandang konseptual, pertanyaan ini mirip dengan yang berikut: dapatkah saya sepenuhnya memasang lantai di dapur dengan salinan yang sama dari setiap ubin di toko? Dalam kehidupan nyata, sebagian besar jenis ubin tidak cocok untuk dapur Anda - untuk benar-benar menutupi lantai, Anda harus menggabungkan bentuknya yang berbeda. Tetapi dalam dunia teori grafik, hipotesis memprediksi bahwa Anda selalu dapat memasang grafik.

Dan di dapur, dan di grafik, penting di mana tepatnya Anda menempatkan ubin pertama. Karya baru ini menyoroti masalah penting ini - dan sedemikian rupa sehingga mengejutkan sekaligus mengejutkan.

Hutan dengan pepohonan


Dalam kombinatorik, matematikawan mempelajari bagaimana simpul (titik) dan tepi (garis) bergabung untuk membentuk objek yang lebih kompleks yang disebut grafik. Anda dapat mengajukan banyak pertanyaan tentang grafik. Salah satu yang mendasar: dalam kasus apa grafik yang lebih kecil dan sederhana idealnya tertanam dalam grafik yang lebih besar dan lebih kompleks?

"Anda memiliki satu set potongan puzzle dan Anda tidak tahu apakah Anda dapat mengumpulkannya dari potongan-potongan ini," kata Jacob Fox dari Universitas Stanford.

Pada 1963, ahli matematika Jerman Gerhard RingelDia mengajukan pertanyaan sederhana namun lebih luas dari jenis ini. Mari kita mulai, katanya, dengan jumlah simpul aneh apa pun yang lebih besar dari 3 (untuk hipotesis yang masuk akal, jumlah simpul pasti ganjil, seperti yang akan kita lihat nanti). Hubungkan dengan ujung-ujungnya sehingga setiap simpul terhubung ke yang lain. Kemudian kita mendapatkan objek yang disebut grafik penuh .



Kemudian bayangkan sebuah grafik dari tipe yang berbeda. Ini bisa menjadi cara sederhana - beberapa sisi terhubung dalam satu baris. Atau jalur dengan tulang rusuk bercabang. Cabang dapat ditambahkan ke cabang lain. Anda dapat membuat grafik yang kompleks semena-mena, menghindari hanya loop tertutup. Grafik semacam itu disebut pohon.



Pertanyaan Ringel berkaitan dengan hubungan grafik dan pohon lengkap. Dia berkata: pertama, bayangkan grafik lengkap dari simpul 2n + 1 (angka ganjil). Kemudian bayangkan pohon apa pun yang terdiri dari n + 1 simpul - dan pohon seperti itu bisa sangat berbeda.

Sekarang ambil salah satu dari pohon-pohon ini dan tempatkan sehingga setiap tepi pohon bertepatan dengan tepi grafik lengkap. Lalu kami menempatkan salinan lain dari pohon yang sama di bagian lain dari grafik lengkap.

Ringel meramalkan bahwa akting dengan cara ini, dan mulai di tempat yang tepat, Anda idealnya bisa menjembatani seluruh grafik lengkap. Ini berarti bahwa setiap tepi grafik lengkap akan ditutupi oleh tepi pohon, dan salinan pohon tidak akan tumpang tindih.



“Aku bisa mengambil salinan pohon itu. Saya menaruh satu salinan di grafik penuh. Dia menutupi beberapa tulang rusuk. Lalu saya ulangi prosesnya. Hipotesis menunjukkan bahwa ini dapat mencakup segalanya, ”kata Benny Sudakov dari Institut Teknologi Federal Swiss, penulis bersama bukti baru, bersama dengan Richard Montgomery dari University of Birmingham dan Alexei Pokrovsky dari Birkbeck College di University of London.

Akhirnya, Ringel memperkirakan bahwa grafik dapat dibuat dari ubin terlepas dari mana dari banyak opsi pohon yang akan Anda gunakan. Pernyataan seperti itu mungkin tampak terlalu umum. Dugaan Ringel berlaku untuk grafik lengkap dengan 11 simpul dan grafik lengkap dengan 11 triliun + 1 simpul. Dan semakin besar grafik lengkap, semakin banyak jumlah pohon yang bisa ditarik untuk n + 1 simpul akan tumbuh. Bagaimana masing-masing dari mereka secara ideal menjembatani grafik lengkap yang sesuai?

Namun, ada alasan untuk percaya bahwa hipotesis Ringel mungkin benar. Konfirmasi pertama adalah bahwa aritmatika kombinatorial yang paling sederhana tidak mengesampingkan opsi seperti itu: jumlah tepi dalam grafik lengkap dengan simpul 2n + 1 selalu dapat sepenuhnya dibagi dengan jumlah tepi pada pohon dengan simpul n +1.

"Fakta bahwa jumlah tepi grafik lengkap dibagi dengan jumlah tepi pohon sangat penting," kata Montgomery.

Matematikawan dengan cepat menemukan bukti lebih lanjut tentang masuk akal hipotesis, yang memicu serangkaian penemuan yang akhirnya mengarah pada bukti.

Tempatkan dan putar


Salah satu pohon paling sederhana adalah bintang: puncak pusat dengan ujung-ujungnya yang memancar darinya. Tetapi berbeda dengan citra khas bintang, karena ujung-ujungnya tidak harus merata di bagian atas. Mereka semua hanya harus datang dari satu tempat, dan tidak boleh berpotongan di mana pun kecuali puncak pusat. Jika Anda ingin membuktikan kebenaran hipotesis Ringel, maka pohon berbentuk bintang akan menjadi titik awal yang alami.



Dan, tentu saja, matematikawan dengan cepat menemukan bahwa bintang n + 1 simpul selalu dengan sempurna membuka grafik lengkap dengan 2n + 1 simpul. Fakta ini menarik dalam dirinya sendiri, tetapi buktinya membuat matematikawan berpikir lebih jauh.

Ambil contoh sederhana. Mari kita mulai dengan 11 puncak. Kami menempatkan mereka dalam lingkaran dan menghubungkan setiap simpul dengan yang lainnya, memperoleh grafik lengkap.



Sekarang perhatikan bintang yang sesuai dengannya: titik pusat dengan lima sisi yang berasal darinya.



Sekarang kita tempatkan bintang sehingga titik pusat bertepatan dengan salah satu simpul dari grafik lengkap. Kami akan membahas beberapa sisi, tetapi tidak semua. Sekarang pindahkan bintang satu simpul, seperti memutar tombol kompas. Kami mendapatkan salinan bintang baru yang ditumpangkan pada set tepi yang sama sekali berbeda dari grafik lengkap.

Kami akan memutar bintang lebih jauh. Pada saat kita kembali ke tempat kita mulai, kita akan membuka seluruh grafik lengkap tanpa melapiskan bintang - persis seperti yang diprediksi Ringel.



"Kita tahu bahwa suatu hipotesis tidak dapat langsung dibuang, setidaknya jika kita mengambil pohon dalam bentuk bintang," kata Sudakov. "Selain itu, kita bahkan dapat menunjukkan ini dengan sangat indah: menggambar grafik pada lingkaran, menggeser bintang, mendapatkan salinan baru, dan mengganti seluruh grafik."

Tak lama setelah Ringel mengemukakan hipotesisnya, ahli matematika Slovakia-Kanada Anton Kotzig menggunakan contoh ini untuk prediksi yang lebih berani daripada Ringel. Ringel mengatakan bahwa setiap grafik lengkap dengan simpul 2n + 1 dapat dipasangkan dengan pohon apa pun dengan simpul n +1, Kotzig menyarankan agar itu dapat disusun dengan cara yang persis sama dengan bintang: dengan menempatkan pohon pada grafik penuh dan hanya memutarnya.

Gagasan itu tampak tidak realistis. Bintang itu simetris, jadi tidak masalah bagaimana menempatkannya. Sebagian besar pohon bengkok. Mereka perlu ditempatkan dengan cara yang sangat spesifik agar metode rotasi berfungsi.

"Bintang itu adalah struktur sederhana yang dapat ditempatkan secara manual, tetapi jika Anda memiliki sebaran pohon di tangan Anda dengan banyak cabang dengan panjang yang berbeda, sulit membayangkan bagaimana ia dapat ditempatkan dengan hati-hati," kata Pokrovsky.

Untuk menyelesaikan hipotesis Ringel menggunakan metode putar Kotsig, matematikawan perlu mengetahui cara menempatkan salinan pohon pertama sehingga belukar yang dapat dilewati tidak akan berubah. Untungnya, mereka menemukan solusi yang penuh warna.

Warna pelangi seringkali membuat hidup lebih mudah. Ini membantu Anda mengatur kalender atau dengan cepat membedakan satu wadah makanan dari yang lain dalam keluarga besar. Ternyata ini juga bisa menjadi cara yang efektif untuk mengetahui cara menempatkan pohon pertama dengan benar di dalam grafik lengkap.

Bayangkan lagi grafik lengkap dengan 11 simpul yang disusun dalam lingkaran. Tandai tepinya dengan kode warna sesuai dengan aturan sederhana yang memperhitungkan jarak antara dua simpul.

Jarak ini ditentukan oleh jumlah langkah yang harus diambil untuk pergi dari satu titik ke titik lainnya dalam lingkaran (tanpa memotong jalur di dalam lingkaran). Tentu saja, dalam lingkaran Anda selalu bisa pergi dalam dua arah, jadi kami akan menentukan jarak sebagai jalur terpendek antara dua puncak. Jika ini adalah simpul bertetangga, maka jarak di antara mereka adalah 1, bukan 10. Jika mereka dipisahkan oleh satu simpul, maka jaraknya adalah 2.



Sekarang kita warnai tepi grafik sesuai dengan jarak. Kami mengecat semua sisi yang menghubungkan puncak yang terletak pada jarak 1 dalam satu warna - misalnya, biru. Kami mengecat semua ujung yang menghubungkan puncak yang terletak pada jarak dua unit di yang lain - misalnya, kuning.

Kami terus mewarnai grafik sehingga semua sisi yang menghubungkan simpul yang berada pada jarak yang sama memiliki warna yang sama. Jarak yang berbeda akan dikodekan dalam warna yang berbeda. Untuk grafik lengkap dengan simpul 2n + 1, Anda perlu n warna untuk ini. Hasilnya adalah gambar yang indah dan bermanfaat.



Tak lama setelah Ringel dan Kotzig mengajukan hipotesis mereka, Kotzig menyadari bahwa mewarnai grafik lengkapnya bisa menjadi panduan untuk menempatkan pohon di atasnya.

Idenya adalah untuk mengatur pohon sehingga menutupi satu tepi setiap warna dan tidak menutupi warna dua kali. Matematikawan menyebut pengaturan ini sebagai replika pelangi dari sebatang pohon. Karena pewarnaan membutuhkan n warna, dan pohon n + 1 simpul akan memiliki n tepi, kita segera tahu bahwa dengan probabilitas tinggi salinan pelangi dapat ditemukan.



Pada akhir 1960-an, matematikawan memahami bahwa salinan pelangi dari sebuah pohon memiliki satu sifat khusus: ini menunjukkan posisi dari mana Anda dapat menjembatani seluruh grafik dengan memutar pohon.

"Jika Anda membuat salinan pelangi, maka semuanya akan berhasil," kata Pokrovsky.

Setelah itu, ahli matematika sudah tahu bahwa mereka dapat membuktikan hipotesis Ringel dengan membuktikan bahwa setiap grafik lengkap dengan simpul 2n + 1 berisi salinan pelangi dari pohon apa pun dengan simpul n + 1. Dan jika salinan pelangi selalu ada, maka Anda selalu dapat menjembatani grafik.

Namun, untuk membuktikan bahwa sesuatu selalu ada itu sulit. Untuk ini, matematikawan harus menunjukkan bahwa grafik lengkap tidak bisa tidak mengandung salinan pelangi pohon. Butuh lebih dari 40 tahun, tetapi inilah yang dicapai Sudakov dan rekan penulisnya dalam sebuah karya baru.

Kemasan yang sempurna


Misalkan Anda diberi grafik lengkap dengan 11 simpul dan satu pohon dengan enam. Grafik lengkap dilukis dalam lima warna berbeda. Pohon itu memiliki lima ujung. Tugas Anda adalah menemukan salinan pelangi dari pohon di dalam grafik lengkap.

Anda bisa menempatkan tepi pohon pada grafik secara bergantian. Yang pertama adalah mudah ditempatkan: Anda dapat memilih tepi warna apa pun untuknya. Yang kedua akan sedikit lebih sulit. Itu bisa terletak hampir di mana saja kecuali untuk tulang rusuk dengan warna yang sama seperti yang baru saja ditutupi. Dan semakin Anda menempatkan tepi pohon, semakin sulit tugasnya. Setelah mencapai tulang rusuk terakhir, Anda akan benar-benar kehilangan pilihan warna - hanya akan ada satu. Masih diharapkan bahwa Anda merencanakan semuanya dengan baik sebelumnya.

Gagasan bahwa tugas menemukan salinan pelangi pohon menjadi lebih rumit ketika Anda menempatkan semakin banyak tepi pohon pada grafik adalah bagian penting dari metode yang digunakan tiga ahli matematika untuk menyelesaikan masalah ini. Mereka mencari cara untuk menjaga fleksibilitas sebanyak mungkin menjelang akhir proses.

Sejak awal, mereka tahu bahwa salinan pelangi dari pohon yang sangat sederhana akan mudah ditemukan - pohon yang terlihat seperti jalan panjang, tanpa cabang atau dengan sedikit. Hal yang paling sulit adalah menempatkan pohon-pohon dengan banyak tepian yang konvergen pada satu titik - seperti bintang, hanya dengan bentuk yang lebih tidak rata dan tidak beraturan. Menempatkan mereka seperti mendorong kereta dorong ke bagasi mobil yang setengah terisi.

"Kesulitan dimulai ketika Anda mencoba mengisi grafik lengkap dengan hal-hal aneh yang terlihat seperti bintang," kata Pokrovsky.

Siapa pun yang mengisi bagasi tahu bahwa Anda selalu harus mulai dengan benda paling rumit - koper besar dan benda tidak fleksibel besar, seperti sepeda. Jaket selalu bisa didorong. Dan matematikawan telah mengadopsi filosofi ini.

Bayangkan sebuah pohon dengan 11 ujung. Enam dari mereka bertemu di titik pusat. Hampir semua yang lain membentuk satu bentuk, jauh dari yang utama.



Bagian tersulit untuk ditempatkan adalah bagian dari pohon yang terdiri dari puncak dengan enam ujung. Oleh karena itu, ahli matematika memisahkannya dari sisa pohon dan menempatkannya terlebih dahulu, sehingga dapat melampirkan bagian ini nanti - seolah-olah Anda memutuskan untuk membongkar tempat tidur sebelum menyeretnya ke lantai dua, dan kemudian memasang kembali di ruang yang diinginkan. Mereka bahkan tidak menempatkan bagian bintang ini di grafik sekali - mereka menemukan berbagai tempat yang cocok untuk menempatkan salinannya di dalam grafik lengkap.

Dan kemudian mereka secara acak memilih satu salinan. Dengan melakukan itu, mereka menjamin bahwa ruang kosong yang tersisa dalam grafik juga acak - yaitu, dengan distribusi tepi yang kurang lebih sama dari warna yang berbeda. Di tempat inilah mereka perlu menempatkan sisa pohon - jalan yang pertama kali mereka sisihkan.

Mereka menghadapi batasan saat memilih opsi untuk penempatannya. Jalan harus dihubungkan ke bintang - bagian dari pohon yang telah mereka tempatkan, dan juga harus menutupi warna yang sebelumnya tidak tertutup oleh bintang yang terhubung dengannya.

Tetapi matematikawan telah meninggalkan opsi untuk diri mereka sendiri. Mereka dapat menghubungkan jalur dengan hampir semua salinan bintang. Apa yang lebih baik, karena ruang di sekitar bintang itu acak, mereka memiliki pilihan untuk memilih warna yang berbeda untuk menutupi dengan sisa pohon.

"Menjelang akhir membangun pohon, ketika situasinya menjadi rumit, saya tidak memiliki satu warna wajib yang tersisa, tetapi pilihan kecil," kata Montgomery.

Tiga matematikawan melengkapi bukti mereka dengan argumen dari teori probabilitas. Mereka menunjukkan bahwa setelah menanam bagian pohon yang paling rumit, asalkan ruang yang tersisa di kolom penuh pada dasarnya acak, akan selalu mungkin untuk menemukan cara untuk membangun di sisa pohon untuk mendapatkan salinan pelangi.

"Sekarang Anda bisa memaksakan apa yang Anda tunda dari awal, seolah-olah untuk menyerap apa yang tersisa dari pohon dan mendapatkan warna pelangi penuh," kata Noga Alon dari Universitas Princeton.

Matematikawan belum menjelaskan cara yang tepat untuk menemukan salinan pelangi untuk setiap pohon dengan n + 1 simpul di setiap grafik lengkap dengan 2n + 1 simpul. Namun, mereka membuktikan bahwa salinan pelangi harus ada di dalamnya.

Dan jika salinan pelangi selalu ada, maka Anda selalu dapat menjembatani grafik dengan metode yang diprediksi oleh Ringel. Dengan demikian, hipotesisnya benar.

Buktinya juga menyediakan alat-alat baru untuk memecahkan masalah yang belum terpecahkan serupa dalam kombinatorik - misalnya, masalah "markup anggun", yang memprediksi bahwa grafik lengkap dapat disusun bahkan dalam kondisi yang lebih ketat, yang menurutnya pohon-pohon harus ditempatkan lebih akurat.

"Ini menunjukkan bahwa metode yang sudah lama dipikirkan orang benar-benar memiliki potensi besar," kata Fox. "Jika Anda menerapkannya dengan benar, Anda dapat memecahkan masalah yang sebelumnya tampaknya tidak dapat ditembus."

More articles:


All Articles