Computing the crosscap number of a knot using integer programming and normal surfaces

Burton, Benjamin A. and Ozlen, Melih (2012) Computing the crosscap number of a knot using integer programming and normal surfaces. ACM Transactions On Mathematical Software, 39 1: 4.1-4.18. doi:10.1145/2382585.2382589


Author Burton, Benjamin A.
Ozlen, Melih
Title Computing the crosscap number of a knot using integer programming and normal surfaces
Journal name ACM Transactions On Mathematical Software   Check publisher's open access policy
ISSN 0098-3500
1557-7295
Publication date 2012-11
Sub-type Article (original research)
DOI 10.1145/2382585.2382589
Volume 39
Issue 1
Start page 4.1
End page 4.18
Total pages 18
Place of publication New York, United States
Publisher Association for Computing Machinery
Collection year 2013
Language eng
Formatted abstract
The crosscap number of a knot is an invariant describing the nonorientable surface of smallest genus that the knot bounds. Unlike knot genus (its orientable counterpart), crosscap numbers are difficult to compute and no general algorithm is known. We present three methods for computing crosscap number that offer varying trade-offs between precision and speed: (i) an algorithm based on Hilbert basis enumeration and (ii) an algorithm based on exact integer programming, both of which either compute the solution precisely or reduce it to two possible values, and (iii) a fast but limited precision integer programming algorithm that bounds the solution from above.

The first two algorithms advance the theoretical state-of-the-art, but remain intractable for practical use. The third algorithm is fast and effective, which we show in a practical setting by making significant improvements to the current knowledge of crosscap numbers in knot tables. Our integer programming framework is general, with the potential for further applications in computational geometry and topology.
Keyword Algorithms
Theory
Experimentation
Crosscap number
Integer programming
Knot genus
Knot theory
Normal surfaces
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ
Additional Notes Article number 4

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
Official 2013 Collection
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 7 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Sun, 13 Jan 2013, 00:11:36 EST by System User on behalf of Scholarly Communication and Digitisation Service