2011/08/31 by Kasra Rafi, Jing Tao
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Euler characteristic #Genus #Lipschitz continuity #Markov Chains and Monte Carlo Methods #Metric (unit) #Moduli #Moduli space #Rank (graph theory) #Space (punctuation) #math.CO #math.GT #msc:05C85 #msc:20F34 #msc:30F60 #semigroups and automata theory
paper · pdf · doi:10.1215/00127094-2323128
published as Duke Math. J. 162, no. 10 (2013), 1833-1876 · 34 pages, 10 figures. Referee's comments incorporated. An appendix section is added to discuss the growth rate of the diameter of the space of graphs equipped with the metric of (non-simultaneous) Whitehead moves. The final version will appear in Duke Mathematical Journal
arxiv created 2013/01/23 · openalex publication_date 2013/07/11 · openalex created_date 2016/06/24 · arxiv updated 2019/12/19 · openalex updated_date 2026/08/05
Let S be a surface of genus g with p punctures with negative Euler characteristic. We study the diameter of the ϵ-thick part of moduli space of S equipped with the Teichmüller or Thurston’s Lipschitz metric. We show that the asymptotic behaviors in both metrics are of order log(g+pϵ). The same result also holds for the ϵ-thick part of the moduli space of metric graphs of rank n equipped with the Lipschitz metric. The proof involves a sorting algorithm that sorts an arbitrarily labeled tree with n labels using simultaneous Whitehead moves, where the number of steps is of order log(n). As a related combinatorial problem, we also compute, in the appendix of this paper, the asymptotic diameter of the moduli space of pants decompositions on S in the metric of elementary moves.