Recognizing trace graphs of closed braids

Thomas Fiedler, Vitaliy KurlinDurham 2008 · DOI

TL;DR

This paper introduces "trace graphs" as a novel combinatorial object to represent closed braids. They prove that these trace graphs uniquely characterize closed braids up to isotopy and provide a polynomial-time algorithm for recognizing them, a significant step towards solving the braid conjugacy problem.

What Problem Does This Paper Address?

The core problem addressed is the classification of closed braids, specifically determining when two closed braids are "isotopic" (can be smoothly deformed into each other). This is equivalent to the conjugacy problem for braid groups, which is notoriously difficult, especially for a larger number of strands. Existing methods often struggle with exponential complexity. The authors aim to find a more efficient, polynomial-time approach.

Methods

The paper's central innovation is the "trace graph." For a closed braid in a solid torus, they consider a one-parameter family of its rotated diagrams. The crossings in these diagrams, over time, form a "trace graph" embedded in a thickened torus. They establish that two closed braids are isotopic if and only if their trace graphs can be transformed into each other via a finite sequence of "trihedral" and "tetrahedral" moves. Crucially, they then develop algorithms to recognize these trace graphs up to isotopy and these specific moves in polynomial time with respect to the braid length.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and algorithms rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Trace Graphs as Canonical Representations: The trace graph provides a richer, more invariant representation of a closed braid than traditional knot diagrams, capturing more topological information.
  • Equivalence via Moves: The key insight is that the equivalence of trace graphs under specific "trihedral" and "tetrahedral" moves directly corresponds to the isotopy of the original closed braids. This provides a concrete set of operations for comparing braids.
  • Polynomial-Time Recognition: The development of algorithms to recognize these trace graphs in polynomial time is a major breakthrough, offering a practical approach to a previously intractable problem.
  • Hierarchical Structure: The trace graph decomposes into "level subgraphs," revealing a hierarchical structure that is crucial for the recognition algorithm.

Key Results

  • Theorem 1.4: Closed braids are isotopic if and only if their trace graphs are related by isotopy in the thickened torus and a finite sequence of trihedral and tetrahedral moves.
  • Theorem 1.5: A polynomial-time algorithm is presented to decide whether two trace graphs are isotopic under these moves. The complexity is C(n/2)n²/8(6l)n²-n+1, where n is the number of strands and l is the braid length. This complexity is significantly reduced for pure braids and knots.
  • Trace Codes: A "trace code" is introduced as a combinatorial representation of a trace graph, enabling efficient comparison.

Limitations and Future Work

  • Complexity: While polynomial, the complexity of the recognition algorithm is still quite high, especially for larger numbers of strands and braid lengths.
  • General Position: The algorithms rely on braids being in "general position," which might require initial deformation steps.
  • Future Work: The paper suggests further exploration into recognizing trace graphs up to trihedral moves (Theorem 1.5), which is a less stringent equivalence than full isotopy. The work also lays the groundwork for understanding the conjugacy problem for braid groups more broadly.

Summary updated

Abstract

To a closed braid in a solid torus we associate a trace graph in a thickened torus in such a way that closed braids are isotopic if and only if their trace graphs can be related by trihedral and tetraherdal moves. For closed braids with a fixed number of strands, we recognize trace graphs up to isotopy and trihedral moves in polynomial time with respect to the braid length.
BibTeX
@inproceedings{fiedler2008recognizing,
  author = {Thomas Fiedler and Vitaliy Kurlin},
  title = {{Recognizing trace graphs of closed braids}},
  booktitle = {Durham},
  year = {2008},
  doi = {10.48550/arxiv.0808.2713},
}
Figure