20. July 2026

Flip Markov chain on sphere triangulations

Figure This figure shows 4 snapshots from the edge flip Markov chain on a simple triangulation of the sphere with 8000 triangles. See the video below for an animated version.

A combinatorial triangulation of the 2-sphere can be visualized in 3D via a force-driven layout of its vertices. These videos show evolving (simple) triangulation of the 2-sphere obtained by repeatedly selecting a uniform random edge and flipping the two neighboring triangles, provided the result is simple again (no loops or multiple edges). It is well-known that the stationary distribution of this process is the uniform simple triangulation, which is an example of a random geometry in the universality class of the Brownian sphere [1]. Establishing the asymptotic mixing time of the edge flip Markov chain is an open problem in the field of random planar maps. See [2] for a lower bound in the case of type-I triangulations and [3] for an upper bound in the case of quadrangulations.

Video The edge flip Markov chain on a simple triangulation of the sphere with 8k triangles.

Video The Markov chain on a simple triangulation of the sphere with 40k triangles captured up close.

Video High speed Markov chain on a simple triangulation of the sphere with 5k triangles.

References

[1] Addario-Berry, Louigi, and Marie Albenque. The scaling limit of random simple triangulations and random simple quadrangulations. (2017): 2767-2825.

[2] Budzinski, Thomas. On the mixing time of the flip walk on triangulations of the sphere. Comptes Rendus. Mathématique 355, no. 4 (2017): 464-471.

[3] Caraceni, Alessandra, and Alexandre Stauffer. Polynomial mixing time of edge flips on quadrangulations. Probab. Theory Relat. Fields 176, 35–76 (2020).