In mathematics, a flip graph is a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
whose
vertices are
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
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
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is ca ...
.
Among noticeable flip graphs, one finds the
1-skeleton
In mathematics, particularly in algebraic topology, the of a topological space presented as a simplicial complex (resp. CW complex) refers to the subspace that is the union of the simplices of (resp. cells of ) of dimensions In other wo ...
of polytopes such as
associahedra or
cyclohedra.
Examples
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
In order theory, a Hasse diagram (; ) is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set ''(S, ≤)'' one represents ...
of the
Tamari lattice
In mathematics, a Tamari lattice, introduced by , is a partially ordered set in which the elements consist of different ways of grouping a sequence of objects into pairs using parentheses; for instance, for a sequence of four objects ''abcd'', the ...
and the
1-skeleton
In mathematics, particularly in algebraic topology, the of a topological space presented as a simplicial complex (resp. CW complex) refers to the subspace that is the union of the simplices of (resp. cells of ) of dimensions In other wo ...
of the
-dimensional
associahedron
In mathematics, an associahedron is an -dimensional convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a string of letters, and the edges correspond to single application of ...
.
This basic construction can be generalized in a number of ways.
Finite sets of points in Euclidean space
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.
Topological surfaces
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. 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
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
In mathematics, particularly in algebraic topology, the of a topological space presented as a simplicial complex (resp. CW complex) refers to the subspace that is the union of the simplices of (resp. cells of ) of dimensions In other wo ...
of the
-dimensional
cyclohedron
In geometry, the cyclohedron is a d-dimensional polytope where d can be any non-negative integer. It was first introduced as a combinatorial object by Raoul Bott and Clifford Taubes and, for this reason, it is also sometimes called the Bott–Taube ...
.
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
Polytopality
Apart from
associahedra and
cyclohedra, a number of
polytopes
In elementary geometry, a polytope is a geometric object with flat sides (''faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an - ...
have the property that their
1-skeleton
In mathematics, particularly in algebraic topology, the of a topological space presented as a simplicial complex (resp. CW complex) refers to the subspace that is the union of the simplices of (resp. cells of ) of dimensions In other wo ...
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
In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...
on
. The subgraph induced by these triangulations in the flip graph of
is the
1-skeleton
In mathematics, particularly in algebraic topology, the of a topological space presented as a simplicial complex (resp. CW complex) refers to the subspace that is the union of the simplices of (resp. cells of ) of dimensions In other wo ...
of a
polytope
In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...
, the secondary polytope of
.
Connectedness
Polytopal flip graphs are, by this property,
connected
Connected may refer to:
Film and television
* ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular''
* '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film
* ''Connected'' (2015 TV ...
. As shown by
Klaus Wagner in the 1930s, the flip graph of the topological sphere is connected. Among the connected flip graphs, one also finds the flip graphs of any finite 2-dimensional set of points. 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.
The flip graph of the vertex set of the
4-dimensional hypercube is known to be connected.
[
] However, it is yet unknown whether the flip graphs of finite 3- and 4-dimensional sets of points are always connected or not.
References
{{Reflist
Application-specific graphs
Geometric graph theory