Pairs of trees that count planar maps

How far apart two triangulations can be treated a flip as a move that can go either way, and measured distances in the resulting graph. Give every flip a direction instead, and the graph becomes an order: one triangulation lies below another if the second can be reached from the first by flips that all go upward. The solid whose corners are triangulations mentioned this order in passing, under the name it has had since Dov Tamari’s thesis of 1951, the Tamari lattice, and noted that it is a lattice — any two elements have a least upper bound and a greatest lower bound. This essay computes the lattice, checks the two descriptions of its order against each other, finds what a lattice that is not graded looks like, and counts its intervals.

The count is the surprise. An interval of an order is a pair of elements with the first below the second, and counting them measures how much of the order is comparable. For the Tamari lattice the counts are 1, 3, 13, 68, 399, 2,530, … and in 2006 Frédéric Chapoton proved that they are given by

$$\frac{2\,(4n + 1)!}{(n + 1)!\,(3n + 2)!},$$

a formula that William Tutte had found in 1962 for a quite different object: the number of planar triangulations — maps on a sphere in which every face is a triangle — with $n + 3$ vertices. Chapoton noticed the coincidence by comparing numbers, as one compares sequences in an encyclopaedia, and proved it by a generating-function argument; Olivier Bernardi and Nicolas Bonichon found a direct bijection in 2009.

Trees, and a list for each #

The figures work with binary trees rather than triangulations, through the correspondence the previous essay described: a triangulation of a polygon with $n + 2$ vertices is a binary tree with $n$ nodes, and a flip is a rotation. Under a rotation in one direction — call it a right rotation — a node’s left child becomes its parent and the node moves down to the right. Directing every flip as a right rotation gives the Tamari order. Its bottom is the tree with every node a left child, the left comb, and its top is the right comb, every node a right child.

Each tree can be summarised by a list of $n$ numbers. Number the nodes from left to right in their natural order — the order in which a binary search tree would hold its keys — and record for each node the size of its right subtree. The left comb’s list is all noughts; the right comb’s is $n - 1, n - 2, \ldots, 1, 0$. Different trees have different lists, and the hero figure labels the fourteen trees on four nodes by them: from 0000 at the bottom to 3210 at the top.

A right rotation at a node moves the node and its right subtree under its former left child, which makes the left child’s right subtree larger and leaves every other node’s right subtree the same size or larger. So a rotation can only raise the list, place by place. That gives one direction of a description of the order that Samuel Huang and Tamari proved in 1972: one tree lies below another exactly when its list is at most the other’s in every place.

Two descriptions of one order #

The other direction is the surprising one — that whenever one list is at most another in every place, a sequence of upward rotations leads from the first tree to the second — and the next figure checks it on every pair.

For five nodes there are 42 trees and $42^2 = 1{,}764$ ordered pairs. The check computes the order twice. Once by rotations: from each tree, every right rotation, and from those, every further rotation, until nothing new appears — the set of trees reachable upward. Once by lists: every tree whose list is place by place at least the starting tree’s. The two sets agree for every starting tree, and both give 399 pairs in order. The list description is the useful one, because comparing two lists takes $n$ steps while searching for a chain of rotations takes as many as there are trees.

A lattice with lopsided operations #

A lattice needs a greatest lower bound for any two elements, and the lists give it at once.

For every pair of trees on up to seven nodes — 184,041 pairs at seven — the place-by-place minimum of the two lists is the list of some tree, and that tree is then below both and above every tree below both: the meet. The place-by-place maximum is not always a tree’s list. On four nodes it fails for 40 of the 196 ordered pairs; for instance the lists 3010 and 3100 have maximum 3110, which belongs to no tree, and the least tree above both, their join, has to be found by raising that list further. The order is a lattice, as Haya Friedman and Tamari proved in 1967, but its two operations are not mirror images, and the asymmetry comes from the lists: a list of right-subtree sizes has to satisfy a nesting condition that the minimum of two valid lists always respects and the maximum need not.

Not graded #

The subsets of a set, ordered by inclusion, form a lattice in which every maximal chain from bottom to top has the same length, the number of elements. Lattices with that property are called graded, and most lattices met early are. The Tamari lattice is not.

Following every chain of covers from the bottom tree to the top one, the lengths run from $n - 1$ to $n(n - 1)/2$, with every length between occurring: for seven nodes, every length from 6 to 21. The shortest chain is the flip distance between the two combs, which correspond to fans at neighbouring vertices of the polygon, and $n - 1$ flips suffice. The longest climbs one step at a time through a sequence in which each rotation raises the sum of the list by exactly one, from 0 to $n(n - 1)/2$. The two extremes differ by a factor of about $n/2$, and in between every length is realised, so no notion of rank — a function that rises by exactly one along every cover — can exist.

Intervals, counted #

The interval count is the number of pairs $(s, t)$ with $s$ below or equal to $t$, and with the list description it is a direct computation: compare every pair of lists.

The counts are 1, 3, 13, 68, 399, 2,530, 16,965, 118,668 and 857,956 for one to nine nodes — the last from comparing all 23,639,044 ordered pairs of the 4,862 trees on nine nodes — and every one equals $2(4n + 1)!/((n + 1)!(3n + 2)!)$. The share of pairs that are comparable falls: about a half at three nodes, under four per cent at nine. That decline is the lattice becoming wide and shallow relative to its size, as most pairs of large trees have lists that cross — one larger in some places, the other in others. Some intervals are easy to count by hand and anchor the total. Every tree lies above the left comb, so the bottom contributes $C_n$ intervals, one for each tree, and every tree lies below the right comb, contributing another $C_n$; the remaining intervals are pairs of trees strictly between the two combs, and it is they that carry the growth from $4^n$ to $(256/27)^n$. On nine nodes the two combs account for 9,723 of the 857,956 intervals, about one in ninety.

A rate shared with planar maps #

Chapoton’s formula is a ratio of factorials, and Stirling’s approximation turns it into a growth rate.

The Catalan numbers grow by a factor approaching 4 at each node, and the interval counts by a factor approaching $256/27 \approx 9.48$, slowly: the ratio is $6.7$ at seven nodes and $8.87$ at forty. The rate $256/27$ is $4^4/3^3$, the exponential growth of Tutte’s planar triangulations, and of many other families of planar maps with triangular faces. Since all ordered pairs grow like $16^n$, comparable pairs become a vanishing share, falling by a factor of about $0.59$ per node.

That a lattice of binary trees should have exactly as many intervals as there are planar triangulations is the kind of coincidence that, in combinatorics, always turns out to be a theorem. Bernardi and Bonichon’s bijection makes it visible: an interval of the Tamari lattice is encoded by a pair of non-crossing paths, a lower and an upper, and such pairs encode the three trees of a Schnyder wood, a way of orienting and colouring the edges of a planar triangulation that Walter Schnyder introduced in 1989 to draw planar graphs on small grids. So a pair of trees, one below the other, is a triangulated sphere in disguise.

What Tutte counted #

A planar triangulation is a graph drawn on a sphere without crossings in which every face, including the outer one when the sphere is flattened onto a page, is a triangle. Tutte counted them rooted — with one edge marked and given a direction, so that symmetric triangulations are counted once for each essentially different way of marking them — and simple, with no two edges joining the same pair of vertices. By Euler’s formula, which every corner pays for itself derived by charging every corner of a solid, a triangulation of the sphere with $v$ vertices has exactly $3v - 6$ edges and $2v - 4$ triangular faces, so the size of a triangulation is fixed by its number of vertices, as the size of a binary tree is fixed by its number of nodes.

The smallest cases can be checked by hand. With four vertices the only triangulation is the tetrahedron, whose four faces are triangles and whose symmetries make every marking of an edge equivalent: one rooted triangulation, and Chapoton’s formula gives one interval for one node. With five vertices the only triangulation is the triangular bipyramid — two tetrahedra glued along a face — and up to its symmetries it can be rooted in three different ways, giving three rooted triangulations against three intervals on two nodes. From six vertices on, the triangulations multiply — thirteen rooted ones with six vertices, sixty-eight with seven — and so do the intervals, in step.

Tutte found the formula by writing down an equation that the generating function of triangulations must satisfy, as the equation a sequence satisfies did for the Catalan numbers with a single quadratic, — removing the root edge and seeing what remains — and solving it with a method of his own, now called the quadratic method, that handles equations with one more unknown than they seem to have room for. The rate $256/27$ that comes out is shared by triangulations of many kinds, and by other maps whose faces are bounded in size, the way twelve pentagons, whatever the hexagons found a fixed count of defects in every map of a given kind: the sphere’s Euler characteristic constrains every such census in the same way.

Three trees in every triangulation #

Bernardi and Bonichon’s bijection passes through a structure that makes the pair of trees visible. Walter Schnyder showed in 1989 that the interior edges of every planar triangulation can be coloured with three colours and oriented so that at every interior vertex there is exactly one outgoing edge of each colour, in a fixed cyclic order, with the incoming edges of each colour falling between the outgoing ones of the other two. Each colour class is then a tree spanning the interior vertices and rooted at one of the three outer vertices. Such a colouring is a Schnyder wood, and every triangulation has at least one.

Schnyder’s own use for them was drawing. Placing each vertex at the point whose coordinates count the faces in the three regions its three outgoing paths cut out gives a drawing of the triangulation with straight edges, no crossings, and every vertex on a grid of side $v - 2$, which settled the size of grid that planar graphs need up to a constant — the question every point at the average of its neighbours left open from the side of Tutte’s averaging method, whose drawings need exponentially fine grids.

The connection to the Tamari lattice is through the minimal Schnyder wood of each triangulation, which is unique. Bernardi and Bonichon encoded it as a pair of non-crossing paths of the kind counting the paths that go wrong counted with the Catalan numbers, and showed that the pairs arising this way are exactly the intervals of the Tamari lattice, the lower path giving the lower tree and the upper path the upper one. The correspondence goes both ways, which is the bijection, and it explains why the two censuses agree term for term rather than merely at the leading rate.

What the counts cannot show #

The figures count intervals up to nine nodes and check the formula there. That the formula holds for every $n$ is Chapoton’s theorem, proved by showing that the generating function of interval counts satisfies the same functional equation as Tutte’s; nothing in the brute-force counts proves it, and the counts could in principle diverge from the formula at a size they do not reach. They do not, and the reason is the theorem, but the reader should see which of the two statements the pictures support.

Nor do the figures exhibit the bijection with planar maps. They show equal numbers and an equal growth rate, which is evidence of a correspondence and not a correspondence. Bernardi and Bonichon’s construction is a sequence of explicit encodings — interval to pair of paths, pair of paths to Schnyder wood, Schnyder wood to triangulation — each easy to state and each a theorem to verify, and drawing it for even a single interval would need a figure of its own.

Still open: other lattices of the same kind #

The Tamari lattice is one member of several families that generalise it, and the interval counts of the generalisations are where open questions live. The m-Tamari lattices of François Bergeron, whose elements are lattice paths of a different slope, have interval counts with product formulas that Bousquet-Mélou, Fusy and Préville-Ratelle proved in 2011, and these too count planar maps of special kinds. The Cambrian lattices of Nathan Reading, attached to reflection groups, have the Tamari lattice as the type-A case; for some of them interval counts are known and for others not. Whether every such product formula comes from a family of planar maps, and why lattices from algebra keep counting maps from topology, is a question about structure that nobody has answered in general.

There is also the original question in the language of trees. One word and four objects found the Catalan numbers counting brackets, paths, triangulations and trees; Chapoton’s numbers count pairs of those objects in order, and a direct, bijective description of an interval as a single object of the same simple kind — a path, a bracketing, a tree — is not known. The planar triangulation is that object, and it is not simple.

Pairs in order #

A lattice built by giving every flip of a polygon a direction has a number of comparable pairs, and that number turned out to be one that Tutte had computed forty-four years before Tamari’s lattice was counted, for maps on a sphere. The figures confirm the order’s two descriptions agree, that it is a lattice whose meet is a place-by-place minimum and whose join is not, that its chains from bottom to top take every length from $n - 1$ to $n(n - 1)/2$, and that its intervals, counted by brute force to nine nodes, follow Chapoton’s formula exactly and grow towards $256/27$ per node. That the count is Tutte’s is a theorem the computation cannot reach, and the reason it is true is a pair of trees hiding in every triangulated sphere.