2
$\begingroup$

How is the knot equivalence problem represented?

By this I mean I am looking for an analogy that compares with graph equivalence. For graph equivalence, we have two graphs $G_1$ and $G_2$ with adjacency matrices $A$ and $B$ respectively and we seek if there is a permutation matrix $P$ with transpose $P'$ such that $A=PBP'$.

Is there an analogous matrix theoretic framework for knot equivalence? For any decision problem input have to be polynomially sized.

$\endgroup$
  • 1
    $\begingroup$ One can consider the knot as a graph with, say, vertices at the crossings labeled in order along a traversal of the knot and each crossing 'decorated' with a value indicating the orientation of the crossing as seen from the perspective of the traversal. $\endgroup$ – Steven Stadnicki Dec 8 '15 at 7:20
  • $\begingroup$ @StevenStadnicki Thank you very much. Could you please provide the exact formal representation below? $\endgroup$ – T.... Dec 8 '15 at 7:26
  • 1
    $\begingroup$ Certainly, though I'll note that you might want to consider migrating this question to cstheory.SE or even cs.SE; IMHO it falls somewhat short of the usual 'research-level' threshold for MO-appropriateness. $\endgroup$ – Steven Stadnicki Dec 8 '15 at 7:31
8
$\begingroup$

By knot, I assume you mean a knot in $S^3$. Typically a knot is encoded as a diagram, which you might think of as a tetravalent planar graph, with some kind of description of undercrossings and overcrossings, say by some kind of labelling of the half edges incident to every vertex. Abstractly, the notion of equivalence is ambient isotopy; combinatorially, in terms of the diagram, there are the three types of Reidemeister moves.

There are other data types used (like self-avoiding cycles in the integer lattice, or triangulations of $S^3$ together with a cycle in its 1-skeleton), but they will all differ essentially from (finite) graphs in the following way: for any given knot type, there will be infinitely many descriptions of it in that data type. So equivalence will not be as "simple" as conjugation by a permutation matrix. Instead, a priori, one must search through an infinite collection of descriptions related by local moves. Improving on this, Lackenby has shown a polynomial bound on the number of Reidemeister moves to recognize an unknot. More generally, given the current state of things, it's entirely possible knot equivalence is in $\mathsf{P}$.

$\endgroup$
  • $\begingroup$ Better than I could have said it. Thank you! $\endgroup$ – Steven Stadnicki Dec 8 '15 at 7:32
  • $\begingroup$ Here's the Lackenby reference: arxiv.org/abs/1302.0180 $\endgroup$ – Eric S. Dec 8 '15 at 7:35
  • $\begingroup$ @EricS. Is there any connection to Seifert matrices? $\endgroup$ – T.... Dec 8 '15 at 7:44
  • $\begingroup$ I'm not sure what you have in mind. From the diagram, one can use the Seifert algorithm to quickly find a Seifert surface. One can then quickly compute a Seifert matrix using the surface. $\endgroup$ – Eric S. Dec 8 '15 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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