Flip graph
In mathematics, a flip graph is a graph whose vertices are combinatorial or geometric objects, and whose edges link two of these objects when they can be obtained from one another by an elementary operation called a flip.
Among notable flip graphs, one finds the 1-skeleton of polytopes such as associahedra[1] or cyclohedra.
, and two triangulations are adjacent in it whenever they differ by a single interior edge.
In this case, the flip operation consists in exchanging the diagonals of a convex quadrilateral.
These diagonals are the interior edges by which two triangulations adjacent in the flip graph differ.
The resulting flip graph is both the Hasse diagram of the Tamari lattice[3] and the 1-skeleton of the
[1] This basic construction can be generalized in a number of ways.
triangulates a circuit (a minimally affinely dependent subset of
is, by Radon's partition theorem, the unique other triangulation of
The conditions just stated, under which a flip is possible, make sure that this operation results in a triangulation of
[4] The corresponding flip graph, whose vertices are the triangulations of
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.
This definition can be straightforwardly extended to bordered topological surfaces.
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
-gon and whose edges correspond to the operation of doing two centrally-symmetric flips is the 1-skeleton of the
[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.
Apart from associahedra and cyclohedra, a number of polytopes have the property that their 1-skeleton is a flip graph.
The subgraph induced by these triangulations in the flip graph of
[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.
[8] In higher dimensional Euclidean spaces, the situation is much more complicated.
[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.
-gon has been obtained by Daniel Sleator, Robert Tarjan, and William Thurston[12] when
For instance Klaus Wagner provided a quadratic upper bound on the diameter of the flip graph of a set of
[15] The diameter of the flip graphs of arbitrary topological surfaces with boundary has also been studied and is known exactly in several cases.
