On the complexity of braids
Preprint
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\^ole in the proofs is played by a technique introduced by Agol, Hass, and Thurston.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- The Minimum Dilatation of Pseudo-Anosov 5-BraidsExperimental Mathematics, 2007
- On a Yang-Baxter map and the Dehornoy orderingRussian Mathematical Surveys, 2002
- Ordering the braid groupsPacific Journal of Mathematics, 1999
- A New Approach to the Word and Conjugacy Problems in the Braid GroupsAdvances in Mathematics, 1998
- A Fast Method for Comparing BraidsAdvances in Mathematics, 1997
- Extremal length estimates and product regions in Teichmüller spaceDuke Mathematical Journal, 1996
- Mapping Class Groups are AutomaticAnnals of Mathematics, 1995
- Combinatorics of Train Tracks. (AM-125)1992
- Braids, Links, and Mapping Class Groups. (AM-82)1975
- Theory of BraidsAnnals of Mathematics, 1947