License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.25
URN: urn:nbn:de:0030-drops-121831
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12183/
Go to the corresponding LIPIcs Volume Portal

Burton, Benjamin A.

The Next 350 Million Knots

pdf-format:
LIPIcs-SoCG-2020-25.pdf (2 MB)

Abstract

The tabulation of all prime knots up to a given number of crossings was one of the founding problems of knot theory in the 1800s, and continues to be of interest today. Here we extend the tables from 16 to 19 crossings, with a total of 352 152 252 distinct non-trivial prime knots.
The tabulation has two major stages: (1) a combinatorial enumeration stage, which involves generating a provably sufficient set of candidate knot diagrams; and (2) a computational topology stage, which involves identifying and removing duplicate knots, and certifying that all knots that remain are topologically distinct. In this paper we describe the many different algorithmic components in this process, which draw on graph theory, hyperbolic geometry, knot polynomials, normal surface theory, and computational algebra. We also discuss the algorithm engineering challenges in solving difficult topological problems systematically and reliably on hundreds of millions of inputs, despite the fact that no reliably fast algorithms for these problems are known.

BibTeX - Entry

@InProceedings{burton:LIPIcs:2020:12183,
  author =	{Benjamin A. Burton},
  title =	{{The Next 350 Million Knots}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12183},
  URN =		{urn:nbn:de:0030-drops-121831},
  doi =		{10.4230/LIPIcs.SoCG.2020.25},
  annote =	{Keywords: Computational topology, knots, 3-manifolds, implementation}
}

Keywords: Computational topology, knots, 3-manifolds, implementation
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020
Supplementary Material: https://regina-normal.github.io/data.html

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI