[en] 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 5n/2 for all g >= 1. Our upper bounds grow at most like [4 - 1/(4g)]n for g >= 2, and at most like 23n/8 for the bordered torus. (C) 2017 Elsevier Ltd. All rights reserved.
Disciplines :
Mathématiques
Auteur, co-auteur :
PARLIER, Hugo ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit
Pournin, Lionel; Univ Paris 13, LIPN, Villetaneuse, France.
Swiss National Science Foundation [PP00P2_128557, PP00P2_153024] Ville de Paris Emergences project "Combinatoire a Paris"
Commentaire :
Hugo Parlier was partially supported by Swiss National Science Foundation grants PP00P2_128557 and PP00P2_153024. Lionel Pournin was partially funded by Ville de Paris Emergences project "Combinatoire a Paris".
