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 notable flip graphs, one finds the 1-skeleton of polytopes such as associahedra or cyclohedra.

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 notable flip graphs, one finds the 1-skeleton of polytopes such as associahedra or cyclohedra. X\mathord{\star}{Y}=\{x\cup{y}:(x,y)\in{X\mathord{\times}{Y}}\}, and \tau^+ is, by Radon's partition theorem, the unique other triangulation of z . The conditions just stated, under which a flip is possible, make sure that this operation results in a triangulation of \mathcal{A} . The corresponding flip graph, whose vertices are the triangulations of \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 \mathcal{A} is the set of the vertices of a convex n -gon.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373838373 under CC BY-SA 4.0; modifications have been made.