Podejścia do GI inspirowane problemem węzłów

Zarówno GI, jak i Knot Problem stanowią problem decydowania o równoważności strukturalnej obiektów matematycznych. Czy są jakieś wyniki ustanawiające powiązania między nimi? Ładne powiązania problemu węzłów z fizyką statystyczną zostały zbadane za pomocą wielomianów węzłów , czy istnieją podobne wyniki dla ? $GI$

Byłoby to szczególnie pomocne, aby wiedzieć, czy są jakieś standardowe wyniki / ostrzeżenia / sugestie / uwagi przed zacząć patrząc na motywowane problemu węzeł. Właściwie zastanawiałem się, czy zaleca się eksplorację w tym kierunku w ramach pracy magisterskiej. Interesuje mnie kwantowe / klasyczne podejście do i problemy algebraiczne. Wszelkie inne sugestie są mile widziane. $GI$ $GI$

cc.complexity-theory reference-request graph-theory graph-isomorphism algebraic-topology DurgaDatta
źródło

z matematycznych grafów izomorficznych : „w pewnym sensie izomorfizm grafów jest łatwy w praktyce, z wyjątkiem zestawu patologicznie trudnych grafów, które wydają się powodować wszystkie problemy. Zatem, w przeciwieństwie do teorii węzłów, nigdy nie było żadnych znaczących par grafów, dla których izomorfizm został nierozwiązany ... Niestety, prawie na pewno nie ma prostego do obliczenia uniwersalnego niezmiennika grafowego, niezależnie od tego, czy jest on oparty na widmie wykresu, czy na jakichkolwiek innych parametrach wykresu (Royle 2004). ”

vzn

Najwyraźniej równoważność węzłów jest również łatwa w praktyce.

Jeffε

Mam podobne pytanie o plakat tutaj physics.stackexchange.com/questions/39328/... także

DurgaDatta

Według mojej wiedzy, nie ma „patologicznie trudnych” węzłów, które powodują wszystkie problemy. Byłoby bardzo interesujące znaleźć rodzinę rozpakowań, które miały kiepski czas działania w różnych programach do rozpoznawania rozpakowań, zarówno w sposób sprawdzalny, jak i eksperymentalny.

Sam Nead

Odpowiedzi:

Jednym z połączeń jest to, że izomorfizm grafów i izomorfizm węzłów są szczególnymi przypadkami 3-różnorodnego homeomorfizmu. W przypadku węzłów dwa węzły są izomorficzne, jeśli ich uzupełnienia (rozmaitości utworzone przez usunięcie punktów węzła z 3 spacji) są homeomorficzne.

W przypadku grafu możliwe jest przekształcenie wykresów w rozmaitości w taki sposób, że wykresy są izomorficzne wtedy i tylko wtedy, gdy rozmaitości są homeomorficzne. W grudniu napisałem komentarz na ten temat w poście w Google+, ale niestety nie w poście, który mogę udostępnić. Konstrukcja ma zacząć się od rozmaitości dla każdego wierzchołka v, w postaci dopełnienia w 3-kulowej wiązce pętli stopnia (v) (połączonych razem we wspólnym wierzchołku). Dla każdej krawędzi ultrafioletu połącz kolektory u i v razem za pomocą operacjii połącz jedną pętlę od u i jedną pętlę od v przez piłkę chirurgiczną. Następnie każdy izomorfizm wykresów podnosi się do homeomorfizmu wynikowego rozmaitości (byłoby to prawdą, nawet gdybyśmy po prostu zastosowali operację 3-sfer bez bukietów), a bukiety zapobiegają dodatkowym homeomorfizmom, które nie pochodzą z wykresu .

David Eppstein
źródło

bardziej ogólne pytanie dotyczy związku między teorią węzłów a teorią grafów. jako jedno z możliwych miejsc do rozpoczęcia jest połączenie między wielomianem Jonesa (używanym do klasyfikacji węzłów) a wielomianem Tutte grafów płaskich. tzn. w teorii węzłów wielomian Tutte'a pojawia się jako wielomian Jonesa przemiennego węzła. (więc może istnieje jakiś związek teorii węzłów z GI na grafach płaskich).

patrz Thms 7,8 w:

Obliczanie wielomianu Tutte wykresu i wielomianu Jonesa naprzemiennego połączenia średniej wielkości Sekine, Imai, Tani

JONES POLYNOMIAL I WYKRESY NA POWIERZCHNIACH OLIVER T. DASBACH, DAVID FUTER, EFSTRATIA KALFAGIANNI, XIAO-SONG LIN I NEAL W. STOLTZFUS

vzn
źródło