14
$\begingroup$

GI and Knot Problem both are problem of deciding structural equivalence of mathematical objects. Are there any results establishing connections between them? Nice connections of knot problem to statistical physics have been explored via knot polynomials, are there similar results for $GI$?

It would be particularly helpful to know if there are any standard results/warnings/suggestions/comments before one start looking into $GI$ motivated by knot problem. Actually, I was wondering if its recommended to explore in this direction for my master's thesis. I am interested in quantum/classical approaches to $GI$ and algebraic problems. Any other suggestions are welcome.

Improve this question
$\endgroup$
4
  • $\begingroup$ from mathworld isomorphic graphs: "n some sense, graph isomorphism is easy in practice except for a set of pathologically difficult graphs that seem to cause all the problems. So, unlike knot theory, there have never been any significant pairs of graphs for which isomorphism was unresolved. ... Unfortunately, there is almost certainly no simple-to-calculate universal graph invariant, whether based on the graph spectrum or any other parameters of a graph (Royle 2004)." $\endgroup$
    – vzn
    Oct 1, 2012 at 15:34
  • 2
    $\begingroup$ Apparently knot equivalence is also easy in practice. $\endgroup$
    – Jeffε
    Oct 2, 2012 at 3:49
  • $\begingroup$ I have poster similar question here physics.stackexchange.com/questions/39328/… also $\endgroup$
    – DurgaDatta
    Oct 8, 2012 at 4:54
  • $\begingroup$ To my knowledge, there are no "pathologically difficult" knots that cause all of the problems. It would be very interesting to find a family of unknots that had poor running times on the various unknot recognition programs, either provably or just experimentally. $\endgroup$
    – Sam Nead
    Feb 24, 2014 at 12:00

2 Answers 2

Reset to default
17
$\begingroup$

One connection is that graph isomorphism and knot isomorphism are both special cases of 3-manifold homeomorphism. In the knot case, two knots are isomorphic if their complements (manifolds formed by deleting the points of the knot from 3-space) are homeomorphic.

And in the graph case it's possible to transform graphs into manifolds in such a way that the graphs are isomorphic if and only if the manifolds are homeomorphic. I wrote a comment about this on a Google+ post last December, but unfortunately not on a post I can share. The construction is to start with a manifold for each vertex v, in the form of the complement in a 3-sphere of a bouquet of degree(v) loops (connected together at a common vertex). For each edge uv, connect the manifolds for u and v together by a surgery, and link one loop from u and one loop from v across the surgery ball. Then every isomorphism of graphs lifts to a homeomorphism of the resulting manifold (this would be true even if we just used surgery on 3-spheres without the bouquets) and the bouquets prevent the manifold from having extra homeomorphisms that don't come from the graph.

Improve this answer
$\endgroup$
7
$\begingroup$

the more general question is the connection between knot theory and graph theory. as one possible place to start there is a connection between the Jones polynomial (used to classify knots) and the Tutte polynomial of planar graphs. ie in knot theory, the Tutte polynomial appears as the Jones polynomial of an alternating knot. (so maybe there is some connection of knot theory to GI on planar graphs.)

see thms 7,8 in:

Computing the Tutte Polynomial of a Graph and the Jones Polynomial of an Alternating Link of Moderate Size Sekine, Imai, Tani

THE JONES POLYNOMIAL AND GRAPHS ON SURFACES OLIVER T. DASBACH, DAVID FUTER, EFSTRATIA KALFAGIANNI, XIAO-SONG LIN, AND NEAL W. STOLTZFUS

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.