Ahli matematika Rusia membantah hipotesis 53 tahun tentang pewarnaan jaringan

Hanya tiga halaman yang diperlukan untuk ahli matematika Rusia untuk menggambarkan metode pewarnaan jaringan dari jenis tertentu yang melebihi harapan para ahli

Hipotesis 53 tahun mengenai cara terbaik untuk menetapkan warna ke node jaringan ditolak dalam makalah online. Pekerjaan hanya pada tiga halaman menunjukkan adanya metode untuk mewarnai warna-warna tertentu yang telah melampaui semua harapan para ahli.

Tugas untuk mewarnai jaring [ lihat nomor berwarna / kira-kira. perev. ], terinspirasi oleh pertanyaan pewarnaan peta semacam itu, di mana negara-negara tetangga memiliki warna yang berbeda, telah menjadi fokus penelitian oleh ahli matematika selama hampir 200 tahun. Tugasnya adalah memahami bagaimana mewarnai simpul-simpul dari suatu jaringan tertentu (atau grafik , apa yang disebut oleh para ahli matematika mereka) sehingga setiap dua simpul yang terhubung memiliki warna yang berbeda. Tergantung pada konteksnya, pewarnaan ini dapat memberikan cara yang efektif untuk tempat duduk tamu di pesta pernikahan, mengatur tugas-tugas produksi untuk interval waktu luang, atau bahkan memecahkan sudoku .

Tugas pewarnaan grafik seringkali mudah untuk dirumuskan, tetapi sangat sulit untuk diselesaikan. Bahkan dalam mencari jawaban atas pertanyaan yang dengannya seluruh bidang penelitian ini dimulai, apakah empat warna cukup untuk mewarnai peta ? - Butuh lebih dari seratus tahun (jika Anda tertarik, jawabannya adalah ya).

Tugas yang dipertimbangkan dalam pekerjaan baru, sampai sekarang, tidak dianggap sebagai pengecualian. Itu tidak dapat diselesaikan selama lebih dari 50 tahun, dan itu menyangkut produk tensor - grafik yang terdiri dari kombinasi khusus dari dua grafik yang berbeda (sebut saja G dan H). Produk tensor dari grafik G dan H adalah grafik baru yang lebih besar, masing-masing simpul menunjukkan sepasang simpul dari grafik asli - satu dari G dan satu dari H - sementara dua simpul dari produk tensor terhubung jika kedua simpul yang sesuai di G dan simpul yang sesuai dalam H.

Misalkan Anda adalah seorang guru musik dan Anda perlu menemukan pasangan duet yang baik untuk konser tahun kelima. Anda dapat membuat grafik, simpul yang akan menjadi siswa, dan ikatan antara pasangan akan menunjukkan adanya hubungan yang baik di antara mereka. Kemudian Anda dapat membuat grafik kedua di mana setiap node akan menunjukkan alat musik yang berbeda, dan hubungan di antara mereka adalah adanya lembaran musik untuk duet dari kedua instrumen ini. Dalam produk tensor dari dua grafik ini, akan ada satu simpul untuk setiap kemungkinan penyatuan siswa dan instrumen (katakanlah, Alice dan trombon), dan dua simpul akan terhubung jika dua siswa bekerja bersama dengan baik, dan kedua instrumen tersebut kompatibel.

Pada tahun 1966, Stephen Hedetniemi , sekarang seorang profesor di Clemson University di South Carolina, menyarankan dalam disertasi doktoralnya bahwa jumlah minimum warna yang diperlukan untuk mewarnai produk tensor adalah yang terkecil dari dua warna yang diperlukan untuk mewarnai salah satu dari dua grafik. . "Ini adalah salah satu hipotesis utama dalam teori graf," kata Gil Kalai dari Universitas Ibrani di Yerusalem. "Banyak orang mencoba untuk merenungkannya."

Selama beberapa dekade terakhir, matematikawan telah mengumpulkan segunung bukti, beberapa di antaranya berbicara tentang kebenaran hipotesis, dan beberapa - tentang kepalsuannya. Matematikawan yang berbeda memiliki asumsi yang berbeda tentang opsi mana yang pada akhirnya akan menang. Tetapi semua orang setuju bahwa setidaknya itu adalah tugas yang sulit.

"Secara pribadi, saya pikir hipotesis ini benar, karena sejumlah besar orang pintar mempelajarinya, dan harus membuat contoh tandingan," jika itu ada, kata Anthony Bonato dari Ryerson University di Toronto.

Maka ahli matematika Rusia Yaroslav Nikolaevich Shitov menemukan cara sederhana untuk membuat contoh tandingan, karya tensor yang membutuhkan warna lebih sedikit daripada salah satu dari dua grafik yang menyusunnya. Bukti-bukti keluar "dasar tetapi brilian," kata Pavol Hell dari Simon Fraser University di Burnaby, Kanada.

Grafik tensor sangat terkait dengan pertanyaan tentang pemetaan grafik yang berbeda satu sama lain, dan dalam bidang matematika ini, hipotesis Hedetniemi mungkin merupakan masalah terbuka terbesar, kata Hell. "Ini adalah terobosan besar."

Hangout penuh warna

Untuk membayangkan informasi apa yang dapat diambil dari mewarnai grafik tensor, bayangkan bahwa Anda akan mengundang teman-teman Anda ke real pinggiran kota Anda setiap akhir pekan. Dan, sebagai tuan rumah yang baik, Anda ingin mengumpulkan orang-orang yang akan menikmati kebersamaan satu sama lain.

Anda tahu bahwa beberapa teman Anda akan dapat berteman dengan cepat berdasarkan pekerjaan, sementara yang lain tidak. Anda juga tahu bahwa teman-teman Anda memiliki hobi - cara lain agar para tamu dapat menemukan minat yang sama. Anda berspekulasi bahwa seorang guru menari biola dapat bersenang-senang berbicara dengan instruktur yoga bermain tenis atau mendiskusikan musik dengan seorang petani yang menghasilkan sirup maple dan memainkan piano, tetapi mungkin bukan tentang dia daripada dia akan berbicara dengan ilmuwan politik yang mengumpulkan perangko. Anda ingin setiap pasangan tamu dapat menemukan minat yang sama di akhir pekan, baik itu pekerjaan atau hobi, dan Anda bertanya-tanya berapa banyak pertemuan yang perlu Anda atur untuk memilah semua tamu dari daftar.


Yaroslav Shitov menemukan contoh tandingan dari hipotesis Hedetniemi yang berusia 53 tahun dari teori grafik

Anda dapat membayangkan hubungan berbagai jenis pekerjaan dalam bentuk grafik, simpul-simpulnya adalah karya itu, dan dua karya apa saja akan dihubungkan dengan ujung-ujungnya, di antaranya, kemungkinan besar, tidak akan mungkin menemukan topik pembicaraan yang umum (pendekatan ini mungkin tampak terbalik, namun, dalam konteks pewarnaan) grafik hubungan simpul seperti itu masuk akal, karena kita akan menggunakan warna untuk memisahkan pasangan bermasalah ini). Anda juga dapat membuat grafik, simpul-simpul yang merupakan hobi yang berbeda, dan menghubungkan semua yang tidak kompatibel.

Produk tensor dari kedua grafik ini akan memiliki simpul untuk setiap pasangan hobi-kerja, dan dua simpul akan digabungkan jika kedua hobi kerja dan kedua tidak kompatibel - ini persis situasi yang ingin Anda hindari di akhir pekan. Jika Anda dapat mewarnai simpul dari produk tensor sehingga simpul yang dihubungkan oleh tulang rusuk memiliki warna yang berbeda, ini akan memberi Anda cara untuk membuat daftar tamu untuk akhir pekan yang berbeda: Anda dapat mengundang orang yang terkait dengan simpul hijau ke akhir pekan "hijau", simpul merah ke "merah" ", Dan seterusnya, dan pastikan bahwa tamu yang tidak kompatibel akan ada di daftar pada akhir pekan yang berbeda. Jumlah warna yang Anda gunakan akan memberi tahu Anda berapa hari libur yang harus Anda ambil dalam kalender.

Ini mengikuti dari contoh ini bahwa setiap pewarnaan yang valid dari grafik kerja dapat ditransfer ke produk tensor - Anda cukup mewarnai setiap kombinasi hobi-kerja dengan warna yang sama seperti yang Anda gunakan untuk pekerjaan tersebut. Warna seperti itu akan mengarah pada fakta bahwa pada pertemuan tersebut setiap pasangan tamu akan kompatibel secara eksklusif sesuai dengan minat profesional mereka, terlepas dari hobi mereka.

Dan sebaliknya, setiap pewarnaan yang dapat diterima dari grafik hobi dibawa ke produk tensor. Hedetniemi menyarankan bahwa cara terbaik untuk mewarnai grafik tensor adalah dengan membuat salah satu grafik asli memiliki jumlah warna minimal.

Sekilas, hipotesis Hedetniemi tampaknya tidak mungkin. Lagipula, jika Anda mendasarkan pewarnaan tensor pada pewarnaan grafik yang berfungsi, Anda mengabaikan semua yang Anda ketahui tentang hobi yang kompatibel dengan teman-teman Anda dan berpotensi berbagi tamu yang rukun satu sama lain. Jika Anda menggabungkan semua informasi tentang pekerjaan dan hobi, Anda mungkin dapat menggunakan lebih sedikit bunga dan menikmati akhir pekan yang layak tanpa tamu.

Namun, selama lebih dari 50 tahun, matematikawan tidak dapat menemukan produk tensor tunggal, untuk pewarnaan yang membutuhkan warna lebih sedikit daripada grafik konstituennya. Mereka mampu membuktikan bahwa hipotesis itu benar jika tidak lebih dari empat warna diperlukan untuk mewarnai salah satu dari dua grafik. Hal ini juga berlaku untuk pewarnaan “fraksional” yang lebih umum, ketika setiap simpul dapat diberi kombinasi warna - misalnya, 2/3 kuning dan 1/3 hijau. (Dalam hal pertemuan akhir pekan, ini mungkin terkait dengan situasi di mana ada tiga jurnalis dalam daftar teman Anda, satu di antaranya bermain tenis, dan Anda mengundang dua dari mereka ke akhir pekan "kuning", dan yang ketiga ke "hijau").

Temuan ini menunjukkan bahwa hipotesis itu mungkin benar, tetapi yang lain mengatakan sebaliknya. Sebagai contoh, ahli matematika telah menunjukkan bahwa hipotesis Hedetniemi berantakan untuk grafik yang membutuhkan jumlah warna yang tidak terbatas untuk pewarnaan, atau untuk grafik terarah yang ujung-ujungnya memiliki arah yang disukai. Tetapi, terlepas dari kenyataan bahwa matematikawan membuktikan hipotesis Hedetniemi untuk beberapa kasus dan membantahnya untuk kasus lain, mereka tidak dapat memecahkan masalah di bidang yang awalnya dianggap Hedetniemi: grafik tak berarah terbatas dengan pewarnaan bilangan bulat.

"Semua orang umumnya berpikir itu benar, tetapi sulit untuk membuktikan atau membantahnya," kata Noga Elon dari Universitas Princeton.

Halaman Mewarnai

Shitov menghancurkan semua ketidakpastian ini dengan demonstrasi kepalsuan hipotesis Hedetniemi yang jelas dan sederhana. Dalam karya itu, bukti utama yang sesuai pada satu halaman, diisi dengan matematika, ia menunjukkan cara membuat jenis khusus produk tensor, yang membutuhkan lebih sedikit warna untuk dicat daripada komponen apa pun.

Shitov memulai karyanya dengan mengamati apa yang akan terjadi jika kita menggabungkan grafik G dengan salah satu grafik eksponensial dan memperoleh produk tensornya. Grafik eksponensial memiliki satu simpul untuk masing-masing kemungkinan pewarnaan G dengan jumlah warna tetap tertentu (semua pewarnaan yang dimungkinkan diperbolehkan, tidak hanya yang simpul-simpulnya terhubung memiliki warna yang berbeda). Jika grafik G, misalnya, memiliki 7 simpul, dan ada 5 warna di palet kami, maka grafik eksponensial akan memiliki 5 ⁷ simpul - itulah sebabnya ini disebut eksponensial.


Hipotesis Stephen Hedetniemi tentang jumlah minimum warna untuk mewarnai produk tensor grafik tetap belum dikonfirmasi selama lebih dari 50 tahun

Jika kita kembali ke opsi pewarnaan, di mana simpul yang terhubung harus dari warna yang berbeda, maka kami tidak dapat menjamin bahwa lima warna palet kami akan cukup untuk mewarnai grafik G, dan dengan cara yang sama mereka mungkin tidak cukup untuk mewarnai grafik eksponensial dengan 5 ⁷ simpul . Namun, matematikawan telah lama mengetahui bahwa ada satu grafik yang cukup untuk lima warna: itu adalah produk tensor yang terdiri dari G dan grafik eksponensial.

Faktanya, semua grafik eksponensial memiliki sifat ini: produk tensor yang menggabungkan grafik eksponensial dengan grafik dari mana ia dibuat dapat diwarnai dengan jumlah warna yang persis sama dengan grafik aslinya. Shitov membantah hipotesis Hedetniemi, menunjukkan bagaimana mungkin untuk membuat grafik G sehingga lebih banyak warna diperlukan untuk mewarnai baik itu dan grafik eksponensial.

Hedetniemi menyatakan bahwa ia “sangat senang” dengan penyelesaian situasi dengan hipotesisnya setelah beberapa dekade. Bukti Shitov "memiliki keanggunan, kesederhanaan, dan kualitas tipis," tulisnya dalam email.

Contoh tandingan baru ternyata licik dan inventif, kata ahli matematika, dan itu tidak membutuhkan alat matematika canggih yang rumit. "Untuk spesialis teori grafik, desain ini dapat dijelaskan dalam dua kalimat," kata Kalai.

Mengapa tidak ada yang memperhatikan argumen ini selama lebih dari 50 tahun adalah misteri bagi ahli matematika. "Terkadang permata kecil bersembunyi di bawah tumpukan dedaunan," kata Hell. "Shitov berhasil memahami pertanyaan ini lebih dalam daripada orang lain."

Grafik Shitov berubah menjadi sangat besar: ia tidak menghitung ukuran pastinya, tetapi memperkirakan bahwa grafik G mungkin akan memiliki sekitar ^4.100 simpul, dan grafik eksponensial akan memiliki setidaknya ^4.000 simpul, yaitu lebih dari jumlah perkiraan partikel elementer di alam semesta yang dapat diamati [ sekitar 10 ⁸⁰ / sekitar. perev. ]

Tapi, tentu saja, itu semua tergantung pengamat. Shitov percaya bahwa contoh tandingannya “tidak terlalu besar. Dalam matematika, Anda dapat menemukan contoh tandingan, dibandingkan dengan yang ini akan sangat kecil. "

Dan meskipun Anda tidak mungkin dapat mengundang ^4.000 ke rumah negara Anda, karya Shitov tidak menolak adanya contoh tandingan dari ukuran yang jauh lebih kecil. Tetapi sekarang setelah ahli matematika tahu bahwa hipotesis Hedetniemi adalah salah, pertanyaan alami adalah bagaimana tepatnya itu salah: berapa sedikit warna yang diperlukan untuk mewarnai produk tensor dibandingkan dengan grafik konstituennya, dan berapa jumlah minimum simpul dan tepi yang dapat dimiliki oleh contoh-contoh berlawanan tersebut?

Sementara itu, Elon mengatakan bahwa karya baru itu berisi pelajaran penting bagi semua ahli matematika: "Kadang-kadang alasan mengapa suatu hipotesis begitu sulit untuk dibuktikan adalah bahwa itu salah."