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.

The flip graphs of a quadrilateral (top-left), a pentagon (top-right), and a hexagon (bottom).
Examples of flips in dimension 1 (top-right), 2 (top-left and central row), and 3 (bottom row).

Among noticeable flip graphs, one finds the 1-skeleton of polytopes such as associahedra[1] or cyclohedra.[2]

Examples

edit

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[3] and the 1-skeleton of the  -dimensional associahedron.[1]

This basic construction can be generalized in a number of ways.

Finite sets of points in Euclidean space

edit

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  .[4] 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.

Topological surfaces

edit

Another kind of flip graphs is obtained by considering the triangulations of a topological surface:[5] 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. When this set of arcs is maximal, it decomposes   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  .

In this setting, two triangulations of   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   is the graph whose vertices are the triangulations of   with   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  -gon, as the two coincide when the surface is a topological disk with   points placed on its boundary.

Other flip graphs

edit

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  -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.

Properties

edit

Polytopality

edit

Apart from associahedra and cyclohedra, a number of polytopes have the property that their 1-skeleton is a flip graph. For instance, if   is a finite set of points in  , the regular triangulations of   are the ones that can be obtained by projecting some faces of a  -dimensional polytope on  . The subgraph induced by these triangulations in the flip graph of   is the 1-skeleton of a polytope, the secondary polytope of  .[6]

Connectedness

edit

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   with disconnected flip graphs have been found whenever   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]

Diameter

edit

The maximum number of flips required to transform a triangulation into another is the diameter of the flip graph. The diameter of the flip graph of a convex  -gon has been obtained by Daniel Sleator, Robert Tarjan, and William Thurston[12] when   is sufficiently large and by Lionel Pournin for all  . This diameter is equal to   when  .[13]

The diameter of other flip graphs has been studied. For instance Klaus Wagner provided a quadratic upper bound on the diameter of the flip graph of a set of   unmarked points on the sphere.[7] The current upper bound on the diameter is  ,[14] while the best-known lower bound is  .[15] The diameter of the flip graphs of arbitrary topological surfaces with boundary has also been studied and is known exactly in several cases.[16][17][18]

See also

edit

References

edit
  1. ^ a b Lee, Carl (1989), "The Associahedron and Triangulations of the  -gon", European Journal of Combinatorics, 10 (6): 551–560, doi:10.1016/S0195-6698(89)80072-1, MR 1022776
  2. ^ a b Simion, Rodica (2003), "A type-B associahedron", Advances in Applied Mathematics, 30 (1–2): 2–25, doi:10.1016/S0196-8858(02)00522-5, MR 1979780
  3. ^ Tamari, Dov (1962), "The algebra of bracketings and their enumeration", Nieuw Archief voor Wiskunde, Series 3, 10: 131–146, MR 0146227
  4. ^ a b c De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010). Triangulations, Structures for Algorithms and Applications. Algorithms and Computation in Mathematics. Vol. 25. Springer.
  5. ^ Negami, Seiya (1994), "Diagonal flips in triangulations of surfaces", Discrete Mathematics, 135 (1–3): 225–232, doi:10.1016/0012-365X(93)E0101-9, MR 1310882
  6. ^ Gel'fand, Izrail M.; Zelevinskiĭ, Andrei V.; Kapranov, Mikhail M. (1990), "Newton polytopes of principal A-determinants", Soviet Mathematics - Doklady, 40: 278–281, MR 1020882
  7. ^ a b Wagner, Klaus (1936), "Bemerkungen zum Vierfarbenproblem", Jahresbericht der Deutschen Mathematiker-Vereinigung, 46: 26–32
  8. ^ Lawson, Charles L. (1972), "Transforming triangulations", Discrete Mathematics, 3: 365–372, doi:10.1016/0012-365X(72)90093-3, MR 0311491
  9. ^ Santos, Francisco (2000), "A point set whose space of triangulations is disconnected", Journal of the American Mathematical Society, 13: 611–637, doi:10.1090/S0894-0347-00-00330-1, hdl:10902/2584, MR 1758756
  10. ^ Santos, Francisco (2005), "Non-connected toric Hilbert schemes", Mathematische Annalen, 332: 645–665, arXiv:math/0204044, doi:10.1007/s00208-005-0643-5, MR 2181765
  11. ^ Pournin, Lionel (2013), "The flip-Graph of the 4-dimensional cube is connected", Discrete & Computational Geometry, 49: 511–530, arXiv:1201.6543, doi:10.1007/s00454-013-9488-y, MR 3038527
  12. ^ Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). "Rotation distance, triangulations, and hyperbolic geometry". Journal of the American Mathematical Society. 1 (3): 647–681. doi:10.1090/s0894-0347-1988-0928904-4.
  13. ^ Pournin, Lionel (2014). "The diameter of associahedra". Advances in Mathematics. 259: 13–42. arXiv:1207.6296. doi:10.1016/j.aim.2014.02.035. MR 3197650.
  14. ^ Bose, Prosenjit; Verdonschot, Sander (2012). "A History of Flips in Combinatorial Triangulations". Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. p. 29–44. doi:10.1007/978-3-642-34191-5_3. ISBN 978-3-642-34190-8. ISSN 0302-9743.
  15. ^ Frati, Fabrizio (2017). "A Lower Bound on the Diameter of the Flip Graph". Electronic Journal of Combinatorics. 24 (1): P1.43. arXiv:1508.03473. doi:10.37236/5489.
  16. ^ Parlier, Hugo; Pournin, Lionel (2017). "Flip-graph moduli spaces of filling surfaces". Journal of the European Mathematical Society. 19 (9): 2697–2737. arXiv:1407.1516. doi:10.4171/JEMS/726.
  17. ^ Parlier, Hugo; Pournin, Lionel (2018). "Modular flip-graphs of one holed surfaces". European Journal of Combinatorics. 67: 158–173. arXiv:1510.07664. doi:10.1016/j.ejc.2017.07.003.
  18. ^ Parlier, Hugo; Pournin, Lionel (2018). "Once punctured disks, non-convex polygons, and pointihedra". Annals of Combinatorics. 22 (3): 619–640. arXiv:1602.04576. doi:10.1007/s00026-018-0393-1.