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. Flip graphs are special cases of geometric graphs. Among noticeable flip graphs, one finds the 1-skeleton of polytopes such as associahedra or cyclohedra. A prototypical flip graph is that of a convex -gon . The vertices of this graph are the triangulations of , 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 and the 1-skeleton of the -dimensional associahedron. This basic construction can be generalized in a number of ways. Let be a triangulation of a finite set of points . Under some conditions, one may transform into another triangulation of by a flip. This operation consists in modifying the way triangulates a circuit (a minimally affinely dependent subset of ). More precisely, if some triangulation of a circuit is a subset of , and if all the cells (faces of maximal dimension) of have the same link in , then one can perform a flip within by replacing by , where and 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 . The corresponding flip graph, whose vertices are the triangulations of 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 is the set of the vertices of a convex -gon. Another kind of flip graphs is obtained by considering the triangulations of a topological surface: consider such a surface , place a finite number of points on it, and connect them by arcs in such a way that any two arcs never cross.