# Regular Flip Equivalence of Surface Triangulations

## 1. Results on flip equivalence

Let $`F`$ be a closed surface and let $`\chi (F)`$ be its Euler characteristic. A singular triangulation of $`F`$ is a graph $`T`$ embedded in $`F`$ such that each face of $`FT`$ is bounded by an edge path of length three. We denote by $`v(T)`$, $`e(T)`$ and $`f(T)`$ the number of vertices, edges and faces of $`T`$. If $`T`$ is without loops and multiple edges and has more than three faces, then $`T`$ corresponds to a triangulation of $`F`$ in the classical meaning of the word; in order to avoid confusions, we use for it the term regular triangulation.

Let $`e`$ be an edge of a singular triangulation $`T`$ and suppose that there are two distinct faces $`\delta _1`$ and $`\delta _2`$ adjacent to $`e`$. The faces $`\delta _1`$ and $`\delta _2`$ form a (possibly degenerate) quadrilateral, containing $`e`$ as a diagonal. A flip of $`T`$ along $`e`$ replaces $`e`$ by the opposite diagonal of this quadrilateral, see Figure 1.

The flip is called regular, if both $`T`$ and the result of the flip are regular triangulations. Two singular (resp. regular) triangulations $`T_1`$, $`T_2`$ of a closed surface are called flip equivalent (resp. regularly flip equivalent), if they are related by a finite sequence of flips (resp. regular flips) and isotopy.

The following result is well known, and there are many proofs for it. There are interesting applications to the automatic structure of mapping class groups, see  or .

###### Lemma 1.

Any two singular triangulations $`T_1`$ and $`T_2`$ of a closed surface $`F`$ with $`v(T_1)=v(T_2)`$ are flip equivalent.∎

One might ask whether any two regular triangulations of $`F`$ with the same number of vertices are *regularly* flip equivalent. The answer is “Yes” in special cases: any two regular triangulations of the sphere , the torus , the projective plane or the Klein bottle  with the same number of vertices are regularly flip equivalent. But in general, the answer is “No”: it is known that there are 59 different triangulations of the closed oriented surface of genus six based on the complete graph with 12 vertices, see . Such a triangulation does not admit any regular flip, thus the different triangulations are not regularly flip equivalent.

This paper is devoted to the proof of the following theorem. A preliminary version of this paper has been appeared in .

###### Theorem 1.

Let $`F`$ be a closed surface and $`N(F)=94506020\chi (F)`$. Any two regular triangulations $`T_1`$ and $`T_2`$ of $`F`$ with $`v(T_1)=v(T_2)N(F)`$ are regularly flip equivalent.

Negami  stated the mere existence of $`N(F)`$ without an estimate. The estimate in Theorem 1 is far from being best possible, at least for the surfaces up to genus one. The number $`N(F)`$ is negative if and only if $`F`$ is a sphere, in which case the statement is true since the transformation by regular flips is always possible, by Wagner’s Theorem . We assume in the following that $`F`$ is not the sphere.

## 2. Proof of the Theorem

We need some additional notions. A contraction of a regular triangulation $`T`$ along an edge $`e`$ shrinks $`e`$ to a vertex and eliminates the two faces adjacent to $`e`$, see Figure 2.

The edge $`e`$ is called contractible if the result of the contraction is still a regular triangulation. A regular triangulation $`T`$ is called irreducible if it does not contain contractible edges. The number of vertices of irreducible triangulations is bounded by the following result of Nakamoto and Ota .

###### Proposition 1.

If $`T`$ is an irreducible triangulation of a closed surface $`F`$ which is not the sphere, then $`v(T)270171\chi (F)`$. ∎

Let $`\delta `$ be a face of a regular triangulation $`T`$. A face subdivision of $`T`$ along $`\delta `$ replaces $`\delta `$ by the cone over its boundary, see Figure 3,

and the result is denoted $`s_\delta T`$. If $`\delta `$ and $`\delta ^{}`$ are two faces of $`T`$, then $`s_\delta T`$ and $`s_\delta ^{}T`$ are regularly flip equivalent, which is easy to see. Let $`T_1`$ and $`T_2`$ be regular triangulations and $`\delta _1`$, $`\delta _2`$ faces of $`T_1`$, $`T_2`$. It follows that if $`T_1`$ and $`T_2`$ regularly flip equivalent, then so are $`s_{\delta _1}T_1`$ and $`s_{\delta _2}T_2`$. If $`T_2`$ is obtained from $`T_1`$ by $`m`$ successive face subdivisions, then we write $`T_2=s^m(T_1)`$. The notation is ambiguous, but by the preceding remark only up to regular flip equivalence. After these preliminaries, we can cite a lemma of Negami .

###### Lemma 2.

Let $`T_1`$ and $`T_2`$ be regular triangulations of $`F`$. If $`T_2`$ is obtained by contracting some edges of $`T_1`$, then $`T_1`$ is regularly flip equivalent to $`s^m(T_2)`$, with $`m=v(T_1)v(T_2)`$.∎

Let $`T^{}`$ denote the barycentric subdivision of a singular triangulation $`T`$ of $`F`$.

###### Lemma 3.

Let $`T_1`$ and $`T_2`$ be two singular triangulations of $`F`$ with $`v(T_1)=v(T_2)`$. Then $`T_1^{\prime \prime }`$ and $`T_2^{\prime \prime }`$ are regularly flip equivalent.

###### Proof.

It is easy to verify that $`T_1^{\prime \prime }`$ and $`T_2^{\prime \prime }`$ are regular triangulations of $`F`$. By Proposition 1, we know that $`T_1`$ and $`T_2`$ are related by not necessarily regular flips. Let $`T_2`$ be obtained from $`T_1`$ by a single flip. Then $`T_1^{}`$ can be transformed into $`T_2^{}`$ by the sequence of flips and isotopies that is explicitly given in Figure 4.

The edges of $`T_i`$ are drawn bold, and the edges of $`T_i^{}`$ under flip are dotted. None of these flips introduces a loop. It is possible that some flip for $`T_i^{}`$ introduces a multiple edge. This happens only if some of the vertices $`A`$, $`B`$, $`C`$ and $`D`$ of $`T_1`$ coincide. We iterate the construction, i.e., we replace each flip for $`T_i^{}`$ by a flip sequence for $`T_i^{\prime \prime }`$. Since the four vertices of $`T_1^{}`$ of each quadrilateral involved in a flip are pairwise distinct, none of these flips introduces a loop or a multiple edge, thus all flips are regular. ∎∎

###### Corollary 1.

Let $`T_1`$ and $`T_2`$ be two regular triangulations of $`F`$ with $`v(T_1)=v(T_2)`$. Then $`s^m(T_1)`$ and $`s^m(T_2)`$ are regularly flip equivalent, with $`m=35\left(v(T_1)\chi (F)\right).`$

###### Proof.

For any singular triangulation $`T`$ of $`F`$, we have $`v(T^{})=v(T)+e(T)+f(T)`$. Since $`2e(T)=3f(T)`$, we obtain $`f(T)=2(v(T)\chi (F))`$ and $`v(T^{})=6v(T)5\chi (F)`$. It follows easily that $`v(T_i^{\prime \prime })v(T_i)=m`$ for $`i=1,2`$.

One obtains $`T_i^{\prime \prime }`$ from $`T_i`$ by $`m`$ face subdivisions and some regular flips, see Figure 5

for the first barycentric subdivision. The figure shows the neighbourhood of a face, and the edges under flip are dotted. So $`s^m(T_1)T_1^{\prime \prime }T_2^{\prime \prime }s^m(T_2)`$ by the preceding Lemma. ∎∎

Now we finish the proof of Theorem 1. Let $`T_1`$, $`T_2`$ be two regular triangulations of $`F`$ with $`v(T_1)=v(T_2)=MN(F)`$ with

$$N(F)=35\left(\left(270171\chi (F)\right)\chi (F)\right)=94506020\chi (F).$$

By contractions along some edges, $`T_i`$ ($`i\{1,2\}`$) can be transformed into an irreducible triangulation $`S_i`$. By Lemma 2, $`T_i`$ is regularly flip equivalent to $`s^{Mv(S_i)}S_i`$. By Proposition 1 and Corollary 1, $`s^{N(F)v(S_1)}S_1`$ and $`s^{N(F)v(S_2)}S_2`$ are regularly flip equivalent, and so are also $`s^{Mv(S_1)}S_1`$ and $`s^{Mv(S_2)}S_2`$ after further face subdivisions. Therefore also $`T_1`$ and $`T_2`$ are regularly flip equivalent. q.e.d.