Enfoques de GI inspirados en el problema del nudo

14

GI y Knot Problem, ambos son problemas para decidir la equivalencia estructural de los objetos matemáticos. ¿Hay algún resultado que establezca conexiones entre ellos? Se han explorado buenas conexiones del problema de nudos con la física estadística a través de polinomios de nudos , ¿hay resultados similares para ?solyo

En particular, sería útil saber si hay resultados / avisos / sugerencias / comentarios estándar antes de que uno empezar a buscar en motivado por un problema nudo. En realidad, me preguntaba si se recomienda explorar en esta dirección para mi tesis de maestría. Estoy interesado en enfoques cuánticos / clásicos de G I y problemas algebraicos. Cualquier otra sugerencia es bienvenida.solyosolyo

DurgaDatta
fuente
de los gráficos isomórficos del mundo matemático : "en cierto sentido, el isomorfismo gráfico es fácil en la práctica, excepto por un conjunto de gráficos patológicamente difíciles que parecen causar todos los problemas. Entonces, a diferencia de la teoría de nudos, nunca ha habido pares significativos de gráficos para los cuales el isomorfismo no se resolvió ... Desafortunadamente, casi con certeza no existe un gráfico universal invariante de gráfico fácil de calcular, ya sea basado en el espectro del gráfico o en cualquier otro parámetro de un gráfico (Royle 2004) ".
vzn
2
Aparentemente, la equivalencia de nudos también es fácil en la práctica.
Jeffε
Tengo una pregunta similar al póster aquí physics.stackexchange.com/questions/39328/… también
DurgaDatta
Que yo sepa, no hay nudos "patológicamente difíciles" que causen todos los problemas. Sería muy interesante encontrar una familia de no nudos que tuviera tiempos de ejecución pobres en los diversos programas de reconocimiento de nudos, ya sea de forma comprobable o experimental.
Sam Nead

Respuestas:

17

Una conexión es que el isomorfismo gráfico y el isomorfismo de nudo son casos especiales de homeomorfismo de 3 múltiples. En el caso de los nudos, dos nudos son isomórficos si sus complementos (múltiples formados al eliminar los puntos del nudo del espacio 3) son homeomórficos.

Y en el caso de los gráficos, es posible transformar los gráficos en múltiples de tal manera que los gráficos sean isomórficos si y solo si los múltiples son homeomórficos. Escribí un comentario sobre esto en una publicación de Google+ en diciembre pasado, pero desafortunadamente no en una publicación que puedo compartir. La construcción es comenzar con una variedad para cada vértice v, en forma de complemento en una esfera de 3 bucles de bucles de grado (v) (conectados entre sí en un vértice común). Para cada borde uv, conecte los colectores para u y v juntos mediante una cirugía, y unir un bucle desde u y un bucle desde v a través de la bola de cirugía. Luego, cada isomorfismo de los gráficos se eleva a un homeomorfismo del múltiple resultante (esto sería cierto incluso si solo utilizáramos la cirugía en 3 esferas sin los ramos) y los ramos evitan que el múltiple tenga homeomorfismos adicionales que no provienen del gráfico .

David Eppstein
fuente
7

La pregunta más general es la conexión entre la teoría de nudos y la teoría de grafos. Como un posible lugar para comenzar, existe una conexión entre el polinomio de Jones (utilizado para clasificar nudos) y el polinomio de Tutte de los gráficos planos. es decir, en la teoría de nudos, el polinomio de Tutte aparece como el polinomio de Jones de un nudo alterno. (Entonces, tal vez hay alguna conexión de la teoría de nudos con GI en gráficos planos).

ver thms 7,8 en:

Calcular el polinomio de Tutte de un gráfico y el polinomio de Jones de un enlace alterno de tamaño moderado Sekine, Imai, Tani

EL POLINOMIO DE JONES Y LOS GRÁFICOS SOBRE LAS SUPERFICIES OLIVER T. DASBACH, DAVID FUTER, EFSTRATIA KALFAGIANNI, XIAO-SONG LIN y NEAL W. STOLTZFUS

vzn
fuente