GI und Knotenproblem sind beide das Problem, die strukturelle Äquivalenz von mathematischen Objekten zu bestimmen. Gibt es irgendwelche Ergebnisse, die Verbindungen zwischen ihnen herstellen? Gute Zusammenhänge des Knotenproblems mit der statistischen Physik wurden über Knotenpolynome untersucht. Gibt es ähnliche Ergebnisse für ?
Es wäre besonders hilfreich zu wissen, ob es Standardergebnisse / -warnungen / -vorschläge / -kommentare gibt, bevor man sich mit , das durch Knotenprobleme motiviert ist. Eigentlich habe ich mich gefragt, ob es empfehlenswert ist, diese Richtung für meine Masterarbeit zu erkunden. Ich interessiere mich für quanten / klassische Ansätze zu G I und algebraischen Problemen. Alle anderen Vorschläge sind willkommen.
cc.complexity-theory
reference-request
graph-theory
graph-isomorphism
algebraic-topology
DurgaDatta
quelle
quelle
Antworten:
Ein Zusammenhang besteht darin, dass sowohl der Graphisomorphismus als auch der Knotenisomorphismus Spezialfälle des 3-Mannigfaltigen Homöomorphismus sind. Im Knotenfall sind zwei Knoten isomorph, wenn ihre Komplemente (Mannigfaltigkeiten, die durch Löschen der Knotenpunkte aus dem 3-Raum gebildet werden) homöomorph sind.
Und im Diagrammfall ist es möglich, Diagramme so in Mannigfaltigkeiten umzuwandeln, dass die Diagramme genau dann isomorph sind, wenn die Mannigfaltigkeiten homöomorph sind. Ich habe letzten Dezember einen Kommentar dazu in einem Google+ Post geschrieben, aber leider nicht in einem Post, den ich teilen kann. Die Konstruktion beginnt mit einer Mannigfaltigkeit für jeden Scheitelpunkt v in der Form des Komplements in einer 3-Sphäre eines Straußes von Schleifen des Grades (v) (die an einem gemeinsamen Scheitelpunkt miteinander verbunden sind). Verbinden Sie für jede Kante uv die Verteiler für u und v durch a Operation miteinanderund verknüpfen Sie eine Schleife von u und eine Schleife von v über den Operationsball. Dann steigt jede Isomorphie von Graphen zu einer Homöomorphie der resultierenden Mannigfaltigkeit an (dies wäre auch dann der Fall, wenn wir nur eine Operation an 3 Kugeln ohne die Blumensträuße durchgeführt hätten), und die Blumensträuße verhindern, dass die Mannigfaltigkeit zusätzliche Homöomorphien aufweist, die nicht aus der Grafik stammen .
quelle
die allgemeinere Frage ist die Verbindung zwischen Knotentheorie und Graphentheorie. Als ein möglicher Ausgangspunkt gibt es eine Verbindung zwischen dem Jones-Polynom (zur Klassifizierung von Knoten) und dem Tutte-Polynom planarer Graphen. dh in der Knotentheorie erscheint das Tutte-Polynom als das Jones-Polynom eines alternierenden Knotens. (Vielleicht gibt es einen Zusammenhang zwischen Knotentheorie und GI in ebenen Graphen.)
siehe thms 7,8 in:
Berechnung des Tutte-Polynoms eines Graphen und des Jones-Polynoms eines alternierenden Glieds von mäßiger Größe Sekine, Imai, Tani
DAS JONES-POLYNOM UND DIE GRAFIKEN AUF DEN OBERFLÄCHEN OLIVER T. DASBACH, DAVID FUTER, EFSTRATIA KALFAGIANNI, XIAO-SONG LIN UND NEAL W. STOLTZFUS
quelle