On the complexity of braids

Abstract

We define a measure of "complexity" of a braid which is natural with respect to both an algebraic and a geometric point of view. Algebraically, we modify the standard notion of the length of a braid by introducing generators $\Delta \_ij$, which are Garside-like half-twists involving strings $i$ through $j$, and by counting powered generators $\Delta \_{ij}^k$ as $\log (|k|+1)$ instead of simply $|k|$. The geometrical complexity is some natural measure of the amount of distortion of the $n$ times punctured disk caused by a homeomorphism. Our main result is that the two notions of complexity are comparable. This gives rise to a new combinatorial model for the Teichmueller space of an $n+1$ times punctured sphere. We also show how to recover a braid from its curve diagram in polynomial time. The key rôle in the proofs is played by a technique introduced by Agol, Hass, and Thurston.

Version 2: added section on Teichmueller geometry, removed section on train tracks

References in corpus (4)

• Geometry of the Complex of Curves I: Hyperbolicity
• Minimal stretch maps between hyperbolic surfaces
• An algorithm for the word problem in braid groups
• The Computational Complexity of Knot Genus and Spanning Area

Cited by in corpus (16)

• Braids of entangled particle trajectories
• Finite-Time Braiding Exponents
• Symmetric interval identification systems of order three
• Braidlab: A Software Package for Braids and Loops
• Circuit Complexity of Knot States in Chern-Simons theory
• Using braids to quantify interface growth and coherence in a rotor-oscillator flow
• Aggregation and structural phase transitions of semiflexible polymer bundles: a braided circuit topology approach
• Every braid admits a short sigma-definite representative
• Applications of fast triangulation simplification
• Counting intersections of normal curves
• Curve diagram for Artin group of type B
• Distinguishing virtual braids in polynomial time
• The Relaxation Normal Form of Braids is Regular
• Geometric intersection of curves on punctured disks
• Curve Diagrams, Laminations, and the Geometric Complexity of Braids
• Applications of the Dynnikov coordinate system on the boundary of Teichmüller space