Abordagens de GI inspiradas no problema do nó

14

GI e Knot Problem são problemas para decidir a equivalência estrutural de objetos matemáticos. Existem resultados estabelecendo conexões entre eles? Boas conexões do problema do nó à física estatística foram exploradas através de polinômios do nó ; existem resultados semelhantes para ?GEu

Seria particularmente útil saber se existem resultados / avisos / sugestões / comentários padrão antes de começar a investigar o motivado pelo problema do nó. Na verdade, eu queria saber se é recomendável explorar nessa direção a tese de mestrado. Estou interessado em abordagens quânticas / clássico ao G I e problemas algébricos. Quaisquer outras sugestões são bem-vindas.GEuGEu

DurgaDatta
fonte
dos gráficos isomórficos do mathworld : "em certo sentido, o isomorfismo dos gráficos é fácil na prática, exceto por um conjunto de gráficos patologicamente difíceis que parecem causar todos os problemas. Portanto, diferentemente da teoria dos nós, nunca houve pares significativos de gráficos para os quais o isomorfismo foi resolvido ... Infelizmente, quase certamente não há invariável gráfico universal simples de calcular, seja com base no espectro do gráfico ou em qualquer outro parâmetro de um gráfico (Royle 2004) ".
vzn
2
Aparentemente, a equivalência de nós também é fácil na prática.
Jeffε
Eu tenho cartaz semelhante pergunta aqui physics.stackexchange.com/questions/39328/... também
DurgaDatta
Que eu saiba, não há nós "patologicamente difíceis" que causem todos os problemas. Seria muito interessante encontrar uma família de não-nós que tiveram tempos de execução ruins nos vários programas de reconhecimento de nós, de maneira provável ou apenas experimental.
Sam Nead 24/02

Respostas:

17

Uma conexão é que isomorfismo de gráfico e isomorfismo de nó são casos especiais de homeomorfismo de três variedades. No caso do nó, dois nós são isomórficos se seus complementos (variedades formadas pela exclusão dos pontos do nó do espaço 3) são homeomórficos.

E, no caso dos gráficos, é possível transformar gráficos em variedades de tal maneira que os gráficos sejam isomórficos se e somente se os variedades forem homeomórficos. Escrevi um comentário sobre isso em uma postagem do Google+ em dezembro passado, mas infelizmente não em uma postagem que posso compartilhar. A construção é começar com um coletor para cada vértice v, na forma do complemento em uma esfera 3 de um buquê de loops de grau (v) (conectados juntos em um vértice comum). Para cada borda uv, conecte os manifolds para u e v juntos por uma cirurgiae vincule um loop de u e um loop de v na esfera da cirurgia. Então todo isomorfismo dos gráficos passa para um homeomorfismo do coletor resultante (isso seria verdade mesmo se apenas utilizássemos cirurgia em 3 esferas sem os buquês) e os buquês impedem que o coletor tenha homeomorfismos extras que não provêm do gráfico .

David Eppstein
fonte
7

a questão mais geral é a conexão entre a teoria dos nós e a teoria dos grafos. como um local possível para começar, existe uma conexão entre o polinômio Jones (usado para classificar nós) e o polinômio Tutte dos gráficos planares. isto é, na teoria dos nós, o polinômio de Tutte aparece como o polinômio de Jones de um nó alternado. (então talvez exista alguma conexão da teoria dos nós à IG nos gráficos planares).

veja thms 7,8 em:

Computando o polinômio Tutte de um gráfico e o polinômio Jones de um elo alternado de tamanho moderado Sekine, Imai, Tani

O POLINOMIAL DE JONES E GRÁFICOS EM SUPERFÍCIES OLIVER T. DASBACH, DAVID FUTER, EFSTRATIA KALFAGIANNI, XIAO-SONG LIN e NEAL W. STOLTZFUS

vzn
fonte