Kirby Problem 1.76

Definitions and mathematical statement

A knot diagram is a generic plane projection of an embedded circle, with over/under data at its $n$ crossings. It can be encoded by a finite plane graph with crossing information. The unknot recognition problem returns yes exactly when this diagram represents the ambient isotopy class of a round circle.

First, is there a deterministic recognition algorithm whose worst-case running time is bounded by a polynomial in $n$? The polynomial and its degree must be independent of the input knot. A finite combinatorial encoding is understood, so arbitrarily complicated numerical coordinates are not additional input data.

Second, determine the structure of the unknot Reidemeister graph. Its vertices are diagrams of the unknot modulo planar isotopy, and an edge joins two vertices if one Reidemeister move relates them. The three moves insert or remove a curl, insert or remove a canceling pair of crossings, or move a strand past a crossing. Give useful structural descriptions of this infinite connected graph, including its graph metric and the organization of vertices by crossing number. The second question allows intermediate diagrams with more crossings than either endpoint.

Short English statement

Is unknot recognition possible in polynomial time, and what is the structure of the graph of all unknot diagrams and Reidemeister moves?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 2735 (KP-1.76), Kirby's Problems in Low-Dimensional Topology. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 K3: A New Problem List in Low-Dimensional Topology, Problem 1.76. Expanded formulation of the supplied catalogue statement. https://math.berkeley.edu/sites/default/files/surv-295-ruberman-watermarked-author-pdf.pdf.