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 ?
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.
cc.complexity-theory
reference-request
graph-theory
graph-isomorphism
algebraic-topology
DurgaDatta
fonte
fonte
Respostas:
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 .
fonte
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
fonte