Approches de l'IG inspirées par le problème des nœuds

14

GI et Knot Problem sont tous deux des problèmes de décision d'équivalence structurelle d'objets mathématiques. Y a-t-il des résultats établissant des liens entre eux? De jolies connexions du problème des nœuds à la physique statistique ont été explorées via des polynômes de nœuds , y a-t-il des résultats similaires pour ?gje

Il serait particulièrement utile de savoir s'il existe des résultats / avertissements / suggestions / commentaires standard avant de commencer à examiner motivé par un problème de nœud. En fait, je me demandais s'il était recommandé d'explorer dans cette direction pour ma thèse de maîtrise. Je m'intéresse aux approches quantiques / classiques du G I et des problèmes algébriques. N'importe quelles autres suggestions sont les bienvenues.gjegje

cc.complexity-theory reference-request graph-theory graph-isomorphism algebraic-topology DurgaDatta
la source
à partir des graphes isomorphes de mathworld : "Dans un certain sens, l'isomorphisme des graphes est facile en pratique, sauf pour un ensemble de graphes pathologiquement difficiles qui semblent causer tous les problèmes. ». Malheureusement, il n’existe presque certainement aucun invariant universel simple à calculer, qu’il soit basé sur le spectre du graphique ou sur d’autres paramètres d’un graphique (Royle 2004).»
vzn
2
Apparemment, l'équivalence des nœuds est également facile en pratique.
Jeffε
J'ai une question similaire pour les affiches ici physics.stackexchange.com/questions/39328/… également
DurgaDatta
À ma connaissance, il n'y a pas de nœuds "pathologiquement difficiles" qui causent tous les problèmes. Il serait très intéressant de trouver une famille de nœuds qui avaient des temps de fonctionnement médiocres sur les différents programmes de reconnaissance de nœuds, soit de manière prouvée soit simplement expérimentale.
Sam Nead

Réponses:

17

Une connexion est que l'isomorphisme de graphe et l'isomorphisme de noeud sont tous deux des cas particuliers d'homéomorphisme à 3 variétés. Dans le cas du nœud, deux nœuds sont isomorphes si leurs compléments (variétés formées en supprimant les points du nœud de l'espace 3) sont homéomorphes.

Et dans le cas des graphes, il est possible de transformer des graphes en variétés de manière à ce que les graphes soient isomorphes si et seulement si les variétés sont homéomorphes. J'ai écrit un commentaire à ce sujet sur un post Google+ en décembre dernier, mais malheureusement pas sur un post que je peux partager. La construction doit commencer par une variété pour chaque sommet v, sous la forme du complément dans une sphère à 3 sphères d'un bouquet de boucles de degré (v) (connectées ensemble à un sommet commun). Pour chaque bord uv, connectez les collecteurs pour u et v ensemble par une chirurgieet reliez une boucle de u et une boucle de v à travers la balle de chirurgie. Ensuite, chaque isomorphisme des graphiques se transforme en un homéomorphisme de la variété résultante (ce serait vrai même si nous venons de recourir à la chirurgie sur 3 sphères sans les bouquets) et les bouquets empêchent la variété d'avoir des homéomorphismes supplémentaires qui ne proviennent pas du graphique .

David Eppstein
la source
7

la question plus générale est le lien entre la théorie des nœuds et la théorie des graphes. comme point de départ possible, il existe un lien entre le polynôme de Jones (utilisé pour classer les nœuds) et le polynôme de Tutte des graphes planaires. c'est-à-dire que dans la théorie des nœuds, le polynôme de Tutte apparaît comme le polynôme de Jones d'un nœud alterné. (il y a donc peut-être un lien entre la théorie des nœuds et l'IG sur les graphes planaires.)

voir thms 7,8 in:

Calcul du polynôme de Tutte d'un graphe et du polynôme de Jones d'un lien alternatif de taille moyenne Sekine, Imai, Tani

LE JONES POLYNOMIAL ET LES GRAPHIQUES SUR LES SURFACES OLIVER T. DASBACH, DAVID FUTER, EFSTRATIA KALFAGIANNI, XIAO-SONG LIN ET NEAL W. STOLTZFUS

vzn
la source