Modular flip-graphs of one-holed surfaces. (January 2018)

• Record Type: Journal Article
• Authors: Parlier, Hugo; Pournin, Lionel
• Is Part Of: European journal of combinatorics. Volume 67(2018)
• Page Start: 158
• Page End: 173
• Publication Date: 2018-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2017.07.003
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: We study flip-graphs of triangulations on topological surfaces where distance is measured by counting the number of necessary flip operations between two triangulations. We focus on surfaces of positive genus g with a single boundary curve and n marked points on this curve and consider triangulations up to homeomorphism with the marked points as their vertices. Our results are bounds on the maximal distance between two triangulations. Our lower bounds assert that these distances grow at least like 5 n ∕ 2 for all g ≥ 1 . Our upper bounds grow at most like [ 4 − 1 ∕ ( 4 g ) ] n for g ≥ 2, and at most like 23 n ∕ 8 for the bordered torus.