Strong convexity in flip-graphs

Abstract

The set of triangulations of a surface $\Sigma$ with a prescribed set $X$ of vertices can be endowed with a graph structure $\mathcal{F}(\Sigma ,X)$ called a flip-graph, whose edges connect two triangulations that differ by a single arc. It is known that when $X$ is the vertex set of a convex Euclidean polygon $\mathrm{P}$, the subgraph ${\mathcal{F}}_{\epsilon }(\mathrm{P},X)$ induced in $\mathcal{F}(\mathrm{P},X)$ by the triangulations that contain a given arc $\epsilon$ is strongly convex in the sense that all the geodesic paths in $\mathcal{F}(\mathrm{P},X)$ between two such triangulations remain in that subgraph. Here, we provide a related result that involves a triangle instead of an arc: we show that if the three edges of a triangle $\tau$ appear in (possibly distinct) triangulations along a geodesic path in $\mathcal{F}(\mathrm{P},X)$, then $\tau$ must belong to a triangulation in that path. More generally, we prove that certain $3$\nobreakdash-dimensional simplicial complexes related to the geodesics in $\mathcal{F}(\mathrm{P},X)$ are flag and provide two consequences. The first consequence is that ${\mathcal{F}}_{\epsilon }(\mathrm{P},X)$ is not always strongly convex when $X$ is obtained from the vertex set of $P$ by adding just two points. The second, in the case when $\Sigma$ is a topological surface, is that the number of arc crossings between two triangulations does not allow to approximate their distance in $\mathcal{F}(\Sigma ,X)$ by a factor of less than $3/2$.

48 pages, 27 figures

Cited by in corpus (1)

• The rotation distance of brooms