Short hierarchies for knot complements
Lead Research Organisation:
University of Oxford
Department Name: Mathematical Institute
Abstract
A central problem in low-dimensional topology is to classify knots. In his final published paper, Turing highlighted this: 'No systematic method is yet known by which one can tell whether two knots are the same.' There are now several methods to solve this problem, but what remains unresolved is whether there is an efficient solution. Specifically, the following famous question remains unanswered: can one decide whether a knot diagram represents the unknot in polynomial time? This is known as the 'unknotting problem'.
Marc Lackenby has been working on this and related questions for many years. In a recent breakthrough, he has found an algorithm for unknot recognition that runs in quasi-polynomial time. Specifically, if the input diagram has n crossings, the running time is at most k^((log(n))^3) for some constant k. The main method that he used was hierarchies, which are defined as follows.
One starts with the exterior of the knot, which is a 3-manifold M1. Then one cuts this along a properly embedded surface, giving a manifold M2. This process is repeated, until we reach a manifold ML which is a collection of 3-balls. Here L is the length of the hierarchy. It turns out that, in Lackenby's algorithm, L is the crucial quantity that one seeks to bound. Roughly, he was able to bound the running time by nL. He showed how to find hierarchies with length at most (log(n))2, which then led to the quasi-polynomial bound on running time.
Aim: The main aim of the project is to find and use hierarchies with short length. Indeed, it was shown by Jaco that every knot complement admits a hierarchy with length 4. If one could find such a hierarchy algorithmically, then one would have a polynomial time solution to the unknotting problem!
Of course, this is somewhat ambitious, but there are worthwhile intermediate goals:
- Find other applications of short hierarchies. In particular, can one use them to determine efficiently whether a knot is fibred? Might they be used to show that knot hyperbolicity can be efficiently certified?
- Can short hierarchies be found for specific classes of knots, for example closed braids with bounded index?
- Hierarchies have been used in other contexts, for example, the determination of knot genus by Gabai and Thurston, and the proof of topological rigidity by Waldhausen. Is there any advantage to using short hierarchies in these settings?
Methodology: The methods developed by Lackenby are highly combinatorial, although many are geometrically inspired. They are very new and so it is sensible to try to exploit them at this stage. Nevertheless, the use of hierarchies is well-established: it was initiated by Haken in the 1960s, and so there is a substantial body of theory upon which this project can be based.
Research area: This falls within the EPSRC research area "Geometry & Topology".
No companies or collaborators will be involved.
Marc Lackenby has been working on this and related questions for many years. In a recent breakthrough, he has found an algorithm for unknot recognition that runs in quasi-polynomial time. Specifically, if the input diagram has n crossings, the running time is at most k^((log(n))^3) for some constant k. The main method that he used was hierarchies, which are defined as follows.
One starts with the exterior of the knot, which is a 3-manifold M1. Then one cuts this along a properly embedded surface, giving a manifold M2. This process is repeated, until we reach a manifold ML which is a collection of 3-balls. Here L is the length of the hierarchy. It turns out that, in Lackenby's algorithm, L is the crucial quantity that one seeks to bound. Roughly, he was able to bound the running time by nL. He showed how to find hierarchies with length at most (log(n))2, which then led to the quasi-polynomial bound on running time.
Aim: The main aim of the project is to find and use hierarchies with short length. Indeed, it was shown by Jaco that every knot complement admits a hierarchy with length 4. If one could find such a hierarchy algorithmically, then one would have a polynomial time solution to the unknotting problem!
Of course, this is somewhat ambitious, but there are worthwhile intermediate goals:
- Find other applications of short hierarchies. In particular, can one use them to determine efficiently whether a knot is fibred? Might they be used to show that knot hyperbolicity can be efficiently certified?
- Can short hierarchies be found for specific classes of knots, for example closed braids with bounded index?
- Hierarchies have been used in other contexts, for example, the determination of knot genus by Gabai and Thurston, and the proof of topological rigidity by Waldhausen. Is there any advantage to using short hierarchies in these settings?
Methodology: The methods developed by Lackenby are highly combinatorial, although many are geometrically inspired. They are very new and so it is sensible to try to exploit them at this stage. Nevertheless, the use of hierarchies is well-established: it was initiated by Haken in the 1960s, and so there is a substantial body of theory upon which this project can be based.
Research area: This falls within the EPSRC research area "Geometry & Topology".
No companies or collaborators will be involved.
Organisations
People |
ORCID iD |
| Marc Lackenby (Primary Supervisor) | |
| Filippo Baroni (Student) |
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/W523781/1 | 01/10/2021 | 30/09/2025 | |||
| 2580838 | Studentship | EP/W523781/1 | 01/10/2021 | 30/09/2025 | Filippo Baroni |