Pendekatan untuk GI terinspirasi oleh masalah simpul

Masalah GI dan Knot keduanya merupakan masalah dalam menentukan kesetaraan struktural dari objek matematika. Apakah ada hasil yang membuat koneksi di antara mereka? Koneksi bagus masalah simpul ke fisika statistik telah dieksplorasi melalui simpul polinomial , apakah ada hasil yang serupa untuk ? $GI$

Akan sangat membantu untuk mengetahui apakah ada hasil standar / peringatan / saran / komentar sebelum seseorang mulai melihat ke termotivasi oleh masalah simpul. Sebenarnya, saya bertanya-tanya apakah direkomendasikan untuk mengeksplorasi ke arah ini untuk tesis master saya. Saya tertarik pada pendekatan kuantum / klasik untuk dan masalah aljabar. Saran lain dipersilahkan. $GI$ $GI$

cc.complexity-theory reference-request graph-theory graph-isomorphism algebraic-topology DurgaDatta
sumber

dari mathworld isomorphic graphs : "dalam beberapa hal, graph isomorphism mudah dalam prakteknya kecuali untuk serangkaian grafik yang secara patologis sulit yang tampaknya menyebabkan semua masalah. Jadi, tidak seperti teori simpul, tidak pernah ada pasangan grafik yang signifikan yang isomorfisme belum terselesaikan .... Sayangnya, hampir pasti tidak ada invarian grafik universal yang mudah dihitung, baik berdasarkan spektrum grafik atau parameter grafik lainnya (Royle 2004). "

vzn

Tampaknya kesetaraan simpul juga mudah dalam praktiknya.

Jeff

Saya punya poster pertanyaan serupa di sini physics.stackexchange.com/questions/39328/… juga

DurgaDatta

Setahu saya, tidak ada simpul yang "sulit secara patologis" yang menyebabkan semua masalah. Akan sangat menarik untuk menemukan keluarga yang tidak memiliki bekal yang memiliki waktu menjalankan yang buruk di berbagai program pengenalan yang tidak peduli, baik yang terbukti atau hanya secara eksperimen.

Sam Nead

Jawaban:

Satu hubungan adalah bahwa grafik isomorfisma dan isomorfisme simpul keduanya adalah kasus khusus homeomorfisma 3-manifold. Dalam kasus simpul, dua simpul adalah isomorfis jika komplemennya (manifold yang dibentuk dengan menghapus titik-titik simpul dari ruang 3) bersifat homeomorfik.

Dan dalam kasus grafik dimungkinkan untuk mengubah grafik menjadi manifold sedemikian rupa sehingga grafik isomorfik jika dan hanya jika manifol adalah homeomorfik. Saya menulis komentar tentang ini di posting Google+ Desember lalu, tapi sayangnya tidak pada postingan yang bisa saya bagikan. Konstruksi dimulai dengan bermacam-macam untuk setiap titik v, dalam bentuk pelengkap dalam 3-bola buket derajat (v) loop (terhubung bersama-sama pada titik umum). Untuk setiap tepi uv, sambungkan manifol untuk u dan v bersama dengan operasi, dan hubungkan satu loop dari u dan satu loop dari v melintasi bola operasi. Kemudian setiap isomorfisma grafik terangkat ke homeomorfisma dari manifold yang dihasilkan (ini akan benar bahkan jika kita hanya menggunakan pembedahan pada 3-bola tanpa karangan bunga) dan karangan bunga mencegah manifold memiliki homeomorfisma ekstra yang tidak berasal dari grafik .

David Eppstein
sumber

pertanyaan yang lebih umum adalah hubungan antara teori simpul dan teori grafik. sebagai salah satu tempat yang mungkin untuk memulai ada hubungan antara polinom Jones (digunakan untuk mengklasifikasikan knot) dan polinom Tutte dari grafik planar. yaitu dalam teori simpul, polinomial Tutte muncul sebagai polinom Jones dari simpul bolak-balik. (jadi mungkin ada beberapa hubungan teori simpul ke GI pada grafik planar.)

lihat 7,8 dalam:

Menghitung Tutte Polynomial of the Graph dan Jones Polynomial dari Alternating Link dari Moderate Size Sekine, Imai, Tani

POLONOMIAL DAN GRAFIK JONES TERHADAP OLIVER SURFAC T. DASBACH, DAVID FUTER, EFSTRATIA KALFAGIANNI, XIAO-SONG LIN, DAN NEAL W. STOLTZFUS

vzn
sumber