Flip graph

Let ${\displaystyle T}$ be a triangulation of a finite set of points ${\displaystyle {\mathcal {A}}\subset \mathbb {R} ^{d}}$. Under some conditions, one may transform ${\displaystyle T}$ into another triangulation of ${\displaystyle {\mathcal {A}}}$ by a flip. This operation consists in modifying the way ${\displaystyle T}$ triangulates a circuit (a minimally affinely dependent subset of ${\displaystyle {\mathcal {A}}}$). More precisely, if some triangulation ${\displaystyle \tau ^{-}}$ of a circuit ${\displaystyle z\subset {\mathcal {A}}}$ is a subset of ${\displaystyle T}$, and if all the cells (faces of maximal dimension) of ${\displaystyle \tau ^{-}}$ have the same link ${\displaystyle \lambda }$ in ${\displaystyle T}$, then one can perform a flip within ${\displaystyle T}$ by replacing ${\displaystyle \lambda {\mathord {\star }}\tau ^{-}}$ by ${\displaystyle \lambda {\mathord {\star }}\tau ^{+}}$, where

${\displaystyle X{\mathord {\star }}{Y}=\{x\cup {y}:(x,y)\in {X{\mathord {\times }}{Y}}\},}$

and ${\displaystyle \tau ^{+}}$ is, by Radon's partition theorem, the unique other triangulation of ${\displaystyle z}$. The conditions just stated, under which a flip is possible, make sure that this operation results in a triangulation of ${\displaystyle {\mathcal {A}}}$.[4] The corresponding flip graph, whose vertices are the triangulations of ${\displaystyle {\mathcal {A}}}$ and whose edges correspond to flips between them, is a natural generalization of the flip graph of a convex polygon, as the two flip graphs coincide when ${\displaystyle {\mathcal {A}}}$ is the set of the vertices of a convex ${\displaystyle n}$-gon.

Another kind of flip graphs is obtained by considering the triangulations of a topological surface:[5] consider such a surface ${\displaystyle {\mathcal {S}}}$, place a finite number ${\displaystyle n}$ of points on it, and connect them by arcs in such a way that any two arcs never cross. When this set of arcs is maximal, it decomposes ${\displaystyle {\mathcal {S}}}$ into triangles. If in addition there are no multiple arcs (distinct arcs with the same pair of vertices), nor loops, this set of arcs defines a triangulation of ${\displaystyle {\mathcal {S}}}$.

In this setting, two triangulations of ${\displaystyle {\mathcal {S}}}$ that can be obtained from one another by a continuous transformation are identical.

Two triangulations are related by a flip when they differ by exactly one of the arcs they are composed of. Note that, these two triangulations necessarily have the same number of vertices. As in the Euclidean case, the flip graph of ${\displaystyle {\mathcal {S}}}$ is the graph whose vertices are the triangulations of ${\displaystyle {\mathcal {S}}}$ with ${\displaystyle n}$ vertices and whose edges correspond to flips between them. This definition can be straightforwardly extended to bordered topological surfaces.

The flip graph of a surface generalises that of a ${\displaystyle n}$-gon, as the two coincide when the surface is a topological disk with ${\displaystyle n}$ points placed on its boundary.

A number of other flip graphs can be defined using alternative definitions of a triangulation. For instance, the flip graph whose vertices are the centrally-symmetric triangulations of a ${\displaystyle (2d+2)}$-gon and whose edges correspond to the operation of doing two centrally-symmetric flips is the 1-skeleton of the ${\displaystyle d}$-dimensional cyclohedron.[2] One can also consider an alternative flip graph of a topological surface, defined by allowing multiple arcs and loops in the triangulations of this surface.

Flip graphs may also be defined using combinatorial objects other than triangulations. An example of such combinatorial objects are the domino tilings of a given region in the plane. In this case, a flip can be performed when two adjacent dominos cover a square: it consists in rotating these dominos by 90 degrees around the center of the square, resulting in a different domino tiling of the same region.

Apart from associahedra and cyclohedra, a number of polytopes have the property that their 1-skeleton is a flip graph. For instance, if ${\displaystyle {\mathcal {A}}}$ is a finite set of points in ${\displaystyle \mathbb {R} ^{d}}$, the regular triangulations of ${\displaystyle {\mathcal {A}}}$ are the ones that can be obtained by projecting some faces of a ${\displaystyle (d+1)}$-dimensional polytope on ${\displaystyle \mathbb {R} ^{d}}$. The subgraph induced by these triangulations in the flip graph of ${\displaystyle {\mathcal {A}}}$ is the 1-skeleton of a polytope, the secondary polytope of ${\displaystyle {\mathcal {A}}}$.[6]

Polytopal flip graphs are, by this property, connected. As shown by Klaus Wagner in the 1930s, the flip graph of the topological sphere is connected.[7] Among the connected flip graphs, one also finds the flip graphs of any finite 2-dimensional set of points.[8] In higher dimensional Euclidean spaces, the situation is much more complicated. Finite sets of points of ${\displaystyle \mathbb {R} ^{d}}$ with disconnected flip graphs have been found whenever ${\displaystyle d}$ is at least 5.[4][9][10]

The flip graph of the vertex set of the 4-dimensional hypercube is known to be connected.[11] However, it is yet unknown whether the flip graphs of finite 3- and 4-dimensional sets of points are always connected or not.[4]