14
$\begingroup$

A Seifert surface of a knot is a surface whose boundary is the knot. The genus of a knot is the minimal genus among all the Seifert surfaces of the knot. My question is, is any algorithm known to find the genus of a knot?

Note that it’s been known since the 1980’s that Seifert’s algorithm for finding a Seifert surface does not suffice to find the genus of a knot. To wit, there even exist knots for which Seifert’s algorithm never produces a minimal-genus Seifert surface no matter what diagram of the knot you take.

In any case, is there some diagrammatic knot invariant that allows you to calculate the genus?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
13
$\begingroup$

Jaco and Oertel's paper An algorithm to decide if a three-manifold is a Haken manifold [1984], plus a bit of work, gives a doubly exponential time algorithm to compute the Seifert genus. (In practice their algorithm lies in exp-poly.)

Agol, Hass, and Thurston's paper The computational complexity of knot genus and spanning area reduces the time required to exp-poly (and proves that "genus less than $g$" lies in NP).

Recently announced work of Lackenby Unknot recognition in quasi-polynomial time [2021] gives a Haken hierarchy of the initial knot complement. If this can be improved to be a taut sutured manifold hierarchy, then that will reduce the time required (for the genus problem of a knot in the three-sphere given as a diagram) to quasi-polynomial.

The above (and the other answers) answer the question as asked in its first paragraph. However, its final paragraph asks if the genus can be computed from a "diagrammatic knot invariant". The answer there seems to be "not in general", but this is not a theorem. In particular there are families of knots (fibered, alternating) where the spans of certain polynomial invariants (Alexander, Jones) record the genus.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Whoops. Josh and I answered at almost same time. I'll leave my answer up as I give further references. $\endgroup$
    – Sam Nead
    Commented Sep 21, 2022 at 7:36
  • 1
    $\begingroup$ Where in the Lackenby slides is there discussion of an algorithm to find the genus? $\endgroup$
    – Keshav Srinivasan
    Commented Sep 21, 2022 at 13:23
  • $\begingroup$ He does not discuss any algorithm to find the genus. That is a guess (of mine) of a likely extension of Lackenby's work. Given a diagram his algorithm either finds a spanning disk (and the knot is the unknot) or a Haken hierarchy (and the knot is not the unknot). It seems to me that the techniques will extend to find a taut sutured manifold hierarchy, which thus will give the genus. $\endgroup$
    – Sam Nead
    Commented Sep 21, 2022 at 14:17
  • $\begingroup$ I'll edit my answer to make this more clear. $\endgroup$
    – Sam Nead
    Commented Sep 21, 2022 at 14:18
13
$\begingroup$

There is an algorithm using normal surface theory, originally developed by Haken and Schubert to compute the genus of any knot. These articles are in German, but for a reference in English, one could consult Chapter 4 of Matveev's book. The computational complexity of such an algorithm was analysed by Agol, Hass, and Thurston.

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

I think it's usually easier in practice, but knot Floer homology determines the genus (and is algorithmically computable from a diagram). See Ozsváth and Szabó's paper "Holomorphic disks and genus bounds", Theorem 1.2.

Improve this answer
$\endgroup$
5
$\begingroup$

In addition to the references given in the other answers, Lackenby has shown that recognition of the Seifert genus is in NP. This is based on a taut sutured manifold hierarchy for the knot complement which certifies the genus, and works for knots in any (let’s say) homology sphere.

However, you’re asking for a diagrammatic algorithm. In principle, any diagram can be converted into a triangulation of the complement, and then input to Lackenby’s algorithm. However, I think that the spirit of the question is for an invariant that more directly references the knot projection. Since knot Floer homology computes the genus, a diagrammatic formula for knot Floer homology should suffice. One such option is based on grid diagrams for knots (any knot projection can easily be converted to a grid diagram). The disadvantage of this approach is that the chain complex dimension grows like the factorial of the grid number. Thus another approach is based on Kauffman states, which only grow exponentially with the size of the diagram, and is based explicitly on the knot projection. This version admits efficient computer programs to compute the invariant.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .