1

Lets say I have a diagram of a knot in some notation. What's the fastest algorithm to simplify it? Or asked differently: what algorithms do software usually use? I do not need to put it into the very minimal canonical form, since this is difficult to guarantee, just some form that is likely to be minimal or at least less than the original knot.

There are two methods that I can imagine: (1) program the Reidemeister moves and just keep applying them in some manner. (2) define some measure of energy and somehow gradually try to minimize it.

What I would like is to have a fast method that could process millions of complicated knots.

YCor
  • 60,149
Jake B.
  • 1,423
  • 1
    A related question: https://mathoverflow.net/questions/182961/can-knot-diagrams-be-monotonically-simplified-using-under-moves – Marco Golla Jan 06 '21 at 16:03
  • 1
    "to simplify" is possibly not well-defined, and, if so, not uniquely defined. Assuming it means reducing to some minimal form, should the algorithm output a path of elementary moves? Would you be more specific? – YCor Jan 06 '21 at 17:56
  • 3
    Although this method isn't entirely uniform, a good "first approach" to your problem is to triangulate the exterior, then simplify the triangulation using Pachner moves. This can be done in Snappea and Regina and tends to be fairly effective. This does not give you a visual way of presenting the knot under simplification, but it's perhaps the most effective and practical method I know of. – Ryan Budney Jan 06 '21 at 18:46
  • 1
    A second good technique is to form a presentation for the knot group and simplify that, using a small extension of small cancellation theory. Or perhaps use a combination of this and the previous technique. – Ryan Budney Jan 06 '21 at 18:48
  • 1
    Are you looking for actual algorithms? Tell us a bit more about what you need and we might be able to give a helpful answer. There aren't many actual algorithms of the form you seek, and most proper algorithms are not implemented (fully), at least, not in a way that would be convenient in the generality you appear to be asking about. FYI, there appear to be many threads on this topic: https://mathoverflow.net/questions/144158/what-is-the-state-of-the-art-for-algorithmic-knot-simplification – Ryan Budney Jan 06 '21 at 20:34
  • @RyanBudney, your comment about "a small extension of small cancellation theory" is fascinating. Can you give a good reference? – HJRW Jan 06 '21 at 22:23
  • YCor: Perhaps not well-defined as I stated, but still answerable. Perhaps what I wanted is an algorithm that would obtain a local minimum of crossings numbers? – Jake B. Jan 13 '21 at 15:09

0 Answers0