The solid whose corners are triangulations

The previous rungs treated the triangulations of a polygon as a set to be counted. A set has no structure beyond its size, and this one has a great deal: two triangulations can be near each other or far apart, and the natural notion of a step from one to another is already familiar.

Remove one diagonal. The two triangles it separated merge into a quadrilateral, which has one other diagonal, and putting that one in gives a different triangulation. That move is a flip, and it is the same operation that makes a triangulation Delaunay by repetition, arriving here with no geometry attached.

Two facts about the graph, and neither is obvious #

It is regular. A triangulation of an $n$-gon has $n-3$ diagonals, and each of them can be flipped — the quadrilateral opened by removing a diagonal is always convex, because the polygon is, so the other diagonal always lies inside. So every vertex has degree exactly $n-3$, with no exceptions and no boundary cases. That is unusual: most natural graphs on combinatorial objects have some vertices more constrained than others.

It is connected. Any triangulation can be turned into any other by a sequence of flips, and the standard proof is worth the two sentences it takes. Fix a corner $v$ of the polygon. The fan triangulation joins $v$ to every other corner. Given any triangulation, if it is not the fan, some triangle has $v$ as a non-corner or is not incident to $v$; flipping an appropriate diagonal strictly increases the number of diagonals meeting $v$. Since that number is bounded by $n-3$, the process stops, and it stops at the fan. So every triangulation reaches the fan, and hence any triangulation reaches any other by going via it.

That argument also bounds the distance: at most $2(n-3)$ flips between any two triangulations. Getting the exact diameter is a different matter and is discussed below, because it is one of the harder results in the area.

The graph is the skeleton of a solid #

The hexagon’s flip graph has fourteen vertices, twenty-one edges and every vertex of degree three. A three-regular graph on fourteen vertices could be many things. This one is the edge skeleton of a convex polyhedron, and the polyhedron is called the associahedron.

Counting the faces is where the structure becomes visible, because each kind of face records a different fact about flips.

The squares are pairs of flips that do not interfere. Two diagonals that do not bound a common triangle can be flipped independently: doing the first then the second gives the same triangulation as doing the second then the first, and the four triangulations involved form a four-cycle. A square face is a commuting pair.

The pentagons are the associativity relation. Restrict attention to a pentagonal sub-polygon inside the hexagon; its five triangulations flip round in a cycle of length five. That five-cycle is exactly the pentagon in the flip graph, and it is the reason the solid is named what it is.

Euler’s relation checks out: $14 - 21 + 9 = 2$, with nine faces made of three squares and six pentagons. That the numbers work is not evidence the solid exists — many graphs satisfy Euler’s relation without being polyhedral — but the polytope does exist, and there are several explicit constructions of it, of which the tidiest realises it as a slice of a high-dimensional simplex.

The dimensions line up in a way worth stating before the interpretation arrives. A quadrilateral gives a segment, a pentagon gives a pentagon, a hexagon gives a three-dimensional solid, and an $n$-gon gives an object of dimension $n-3$ — the same $n-3$ that is the number of diagonals and the degree of every vertex. That coincidence is not one: the number of diagonals is the number of independent directions in which a triangulation can be changed, which is what a dimension is.

Why the pentagon is the point #

The name deserves unpacking, because the connection to associativity is not a metaphor.

A triangulation of a polygon with a distinguished edge is a bracketing of a product, by the translation of the previous rung: the polygon’s other sides are the factors, each triangle is a multiplication, and the distinguished edge is the result. A flip is then a single application of the associative law, $(ab)c \to a(bc)$, performed somewhere inside the expression.

With three factors there is one associativity move and two bracketings — a single edge. With four factors there are five bracketings, and the moves between them close into a cycle of length five. That five-cycle is Mac Lane’s pentagon, and it is the coherence condition that says: if a product can be rebracketed from one arrangement to another by two different sequences of associativity moves, the two sequences agree.

So the pentagon faces of the associahedron are not a curiosity of the shape. They are the statement that associativity is coherent, and Mac Lane’s theorem — that the pentagon is the only condition needed, and all higher coherence follows from it — is the statement that the higher associahedra have no faces beyond the ones this pattern generates.

A polytope whose faces are the axioms of a rewriting system is an unusual object, and it is the reason this shape appears far outside combinatorics: in homotopy theory, where Stasheff introduced it in 1963 to characterise spaces with a multiplication associative up to coherent homotopy; in the theory of operads; and in cluster algebras, where the flip graph is the exchange graph of a cluster algebra of type A.

Reading a face as a statement about order #

It is worth working through a square face once, because the picture and the algebra land on the same object and the coincidence is easy to miss.

Take a hexagon with corners $0$ through $5$, and a triangulation containing the diagonals $0\text{–}2$ and $3\text{–}5$. Those two do not bound a common triangle, so flipping either leaves the other available. Flipping $0\text{–}2$ gives $1\text{–}3$; flipping $3\text{–}5$ gives $0\text{–}4$. Do both, in either order, and the result carries $1\text{–}3$ and $0\text{–}4$ and is the same triangulation. Four triangulations, four flips, one square.

In the bracketing language the two diagonals are two multiplications with no factor in common — $(ab)$ and $(cd)$ inside $((ab)(cd))$ — and rebracketing one does not touch the other. A square face is therefore the statement that two independent rewritings commute, which in a rewriting system is the diamond property and is what confluence is proved from.

So the polytope’s two-dimensional faces are precisely its rewriting system’s critical pairs, sorted into the trivial kind (independent moves, giving squares) and the genuine kind (overlapping moves, giving pentagons). A shape whose faces are exactly the cases a confluence proof has to check is a strange and useful thing to have.

What the solid is for #

Three uses, and they are not variations on one another.

Rewriting. A flip graph on any set of objects asks whether a rewriting system is confluent and terminating. Here it is neither in the naive sense — flips are reversible, so nothing terminates — but the fan-directed version above does terminate, which is what the connectivity proof exploits. That pattern of finding a potential function which some directed version of the move increases is the standard tool for such questions.

Search. Enumerating every triangulation of a polygon is done by walking the flip graph, and because the graph is connected and regular, a walk visits everything without bookkeeping about what has been seen — provided the walk is systematic. Reverse-search algorithms do exactly this, with memory proportional to the depth rather than to the number of objects, which is what makes enumerating millions of objects practical.

There is a fourth thing the shape is for, and it is the least expected: it gives the objects a geometry, which lets analytic questions be asked about them. Choosing a triangulation uniformly at random is choosing a vertex of the associahedron uniformly at random, and questions about the typical shape of a random triangulation — how many ears, how deep the dual tree, how far from the fan — become questions about how the vertices are distributed over the solid. The answers turn out to involve the same $n^{-3/2}$ that the generating function predicted, which is not a coincidence but is not obvious either.

The general case, which is the hard one. Everything above is about a convex polygon. Triangulations of a general point set in the plane — where the points may be anywhere, not on a circle — also have a flip graph, and it is also connected, by a harder argument due to Lawson that goes through the Delaunay triangulation as a target instead of the fan. In three dimensions the corresponding graph can be disconnected: there are triangulations of point sets in space from which no flip is possible at all, and they are not the only triangulation of that set. The two-dimensional case is not the easy case of a general theorem; it is the case where the theorem happens to be true.

There is a fourth use that is worth separating out, because it is the one that made the object well known outside its own subject. Cluster algebras. Fomin and Zelevinsky’s classification of cluster algebras of finite type assigns to each a graph whose vertices are the algebra’s clusters and whose edges are mutations, and for type $A_{n-3}$ that graph is exactly this flip graph. The associahedron is then the generalised associahedron of that type, and there is one for every Dynkin diagram — the type $B$ version counts centrally symmetric triangulations of a $2n$-gon, and the pattern continues through the classification.

That connection arrived in 2002, four decades after Stasheff’s construction and two centuries after Euler counted the triangulations, and it is the reason a shape built from a puzzle about polygons now appears in papers about representation theory.

That transport is worth taking seriously rather than noting. The associahedron is usually introduced through bracketings, was constructed by Stasheff through paths in a space of loops, appears in cluster algebra through mutations, and is drawn here through polygons. Four descriptions, one solid, and the only reason anybody knows they are the same is that the bijections between the underlying sets were worked out first.

What is not known #

The diameter of the flip graph is a good example of a question that looks routine and is not. The graph is small, regular, connected and completely explicit; the question is how far apart two vertices can be; and the answer took thirty years.

The bound of $2(n-3)$ from the fan argument is easy. Sleator, Tarjan and Thurston proved in 1988 that the diameter is exactly $2n - 10$ for all sufficiently large $n$, and their proof is a startling piece of work: it embeds the problem in three-dimensional hyperbolic geometry and derives the lower bound from a volume estimate. For thirty years “sufficiently large” was not made explicit; Pournin gave a combinatorial proof in 2014 covering every $n \geq 13$.

A purely combinatorial question whose only known proof for two decades ran through hyperbolic volume is worth remembering as a data point about how far apart a question and its answer can live. It is also a reason to be cautious about the flip graph’s apparent simplicity: regular, connected, small degree, and a diameter that needed hyperbolic geometry.

What the graph looks like from a distance #

Two more facts about the flip graph are worth recording, because both are the kind of thing one would guess wrongly.

It is not vertex-transitive. Every vertex has the same degree, which invites the assumption that all triangulations look alike from inside the graph. They do not: the fan triangulations — those in which every diagonal meets one corner — sit differently from the “snake” triangulations, and a walk started at a fan behaves differently from one started at a snake. The symmetry group of the graph is the symmetry group of the polygon, which is dihedral of order $2n$, and that is far too small to move fourteen vertices onto each other. Regularity is a local condition and transitivity is a global one, and this graph has the first and not the second.

And it is not a lattice, though it is very nearly one. Orienting each flip in a consistent direction — always from the diagonal nearer one fixed corner to the one further — turns the graph into a partial order, and that order is the Tamari lattice. It really is a lattice: any two triangulations have a least upper bound and a greatest lower bound. That is a much stronger statement than connectivity and it is the structure the object is usually studied through, since a lattice supports induction in a way a graph does not.

The Tamari lattice on bracketings is one of the oldest objects here — Tamari defined it in his 1951 thesis, twelve years before Stasheff’s polytope — and the fact that the two are the same object seen twice was not obvious to either of them.

What the pictures cannot show #

The solid is drawn from a spring relaxation, not from a construction. The vertex positions come from letting the graph settle under forces, which produces something readable and is not a proof that a convex realisation exists. The combinatorial facts — fourteen vertices, twenty-one edges, three squares, six pentagons, Euler’s relation — are computed and checked; the convexity is a theorem the picture cites rather than demonstrates.

Only the three-dimensional case can be drawn at all. The associahedron of an $n$-gon has dimension $n - 3$, so the hexagon gives the last one that fits in space. The heptagon’s is four-dimensional with forty-two vertices, and the pattern of faces continues in a way no picture reaches.

And the flip graph drawn as a circle of vertices is a lie about distance. In the first figure the fourteen triangulations are placed evenly round a circle in an arbitrary order, so two that appear adjacent may be several flips apart. Only the edges carry information; the positions carry none.

Where the ladder goes next #

This rung closes the ladder’s first pass. The sequence has been counted by a bijection, identified across six families, solved by an equation, and now given a shape.

Named here as debts, both raised above and not settled: the higher associahedra, whose faces are indexed by the partial triangulations rather than the complete ones, and the flip graph of a general point set, where connectivity is a theorem in the plane and false in space.

Sideways, the counting of a polyhedron’s faces against its corners and edges is Euler’s relation, the question of which combinatorial data can be realised as a convex solid is the one the five regular solids answer for a different constraint, and the flip itself is the move that drives a triangulation towards the Delaunay one.

What is worth carrying away #

A set of objects with a natural move between them is a graph, and a graph that is unusually regular is usually the skeleton of something.

Nothing about triangulating a hexagon suggests a solid. What produces one is that the move — flip a diagonal — is available exactly $n-3$ times from every position, and that pairs of independent moves commute. Regularity gives the vertex figure, commuting pairs give the square faces, and the one genuinely combinatorial relation gives the pentagons. The polytope is what those three facts look like when they are drawn.

The habit worth taking is to ask which pairs of moves commute. The answer is what the two-dimensional faces of the object are, and once the two-dimensional faces are known the shape is nearly determined — which is the same question, asked in a different language, as which order two operations can be performed in.