Computing the Crosscap Number of a Knot Using Integer Programming and Normal Surfaces

作者：Burton Benjamin A^*; Ozlen Melih

来源：ACM Transactions on Mathematical Software, 2012, 39(1): 4.

DOI：10.1145/2382585.2382589

• Algorithms
• Theory
• Experimentation
• Crosscap number
• integer programming
• knot genus
• knot theory
• normal surfaces

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.

• 出版日期2012-11