Random Maps 2 – The Schaeffer Bijection

Posted on August 3, 2014 by dominicyeo

As indicated at the end of the previous post, our aim is to find a natural bijection between the set of pointed, rooted quadrangulations with n faces, and some set of objects based on decorating rooted plane trees with n edges in some fashion. Unlike our previous example, the construction of this bijection is definitely not trivial. It seems like a foolish ambition to explain this without several pictures, so I’m going to focus on some aspects of the analysis which I found challenging, rather than the construction itself.

Anyway, we don’t yet know what the extended set of trees should be. We need an extra factor of $3^n$ , so it is natural to consider adding some sort of labelling of the tree, where for each non-root vertex in turn there are three options. So, given a rooted tree T, we label the vertices such that the root has label 0, and if a parent vertex has label k, any offspring has label k-1, k or k+1. Such a labelling is called admissable, and $\mathbb{T}_n$ is the set of rooted plane trees with n edges and an admissable labelling.

We now demonstrate how to construct an element of $\mathcal{Q}_n$ from an element of $\mathbb{T}_n$ . Various authors had considered this problem to various extents, and so what follows is known as the Cori-Vauquelin-Schaeffer bijection, at least in this course.

Consider a contour exploration of the tree. That is, start out at the root and at all times take first-edge you encounter going clockwise from your current direction. When you arrive at a leaf, you will indeed therefore immediately retrace your most recent step. The key property is that you traverse each edge exactly twice, and so we may think of the tree as having 2n oriented edges. It is more useful to think about corners. A corner is the directed arc (WLOG clockwise) between adjacent edges at a vertex. There is a natural bijection between corners and directed edges, by looking anti-clockwise from the tail of the edge. So the contour process explored the directed edges in some order, and hence explores the corners of the tree. One thing I found confusing initially was switching between considering vertices and corners. I feel in retrospect that the only reason we need the vertices themselves is to induce the labelling onto the corners. These are the only thing we will use in the construction.

As we trace out the contour process, naturally we see different labels. We define the successor of a corner with label k to be the next corner seen in the contour process (taken modulo 2n if necessary) with label k-1. Note that any corner on a vertex with minimal label will not have a successor. To counter this, we add a new vertex, suggestively called $v_*$ , with a single corner (ie no edges yet) and denote this corner to be the successor of the corners in the original tree with minimal label.

To construct our quadrangulation, we simply join up every corner with its successor corner. Note that if you are thinking of the successor of a corner as a vertex (rather than as a corner) you will get in trouble here, as it might be several ways to draw this arc.

The red arcs and vertex v* are added to form the quadrangulation. Note the blue angles indicate the three corners around the vertex labelled -1.

It is not obvious that it is possible to do this so that the arcs do not overlap. However, by considering the label process as you explore via the contour process, it becomes clear that you can discount the possibility of any overlaps one by one. This applies equally to pairs of new arcs overlapping, as well as new arcs overlapping with edges of the original tree. In any case, we remove the edges of the original tree to obtain the quadrangulation.

Note that when you move from any corner of a vertex with label k to its successor, then to the successor of its successor and so on, the labels are decreasing, so eventually you must end up at a corner with minimal label, and hence at $v_*$ . We conclude that the graph of arcs is connected. It remains to show that it is a quadrangulation.

This is rather fiddly to do without a diagram. Note first that whenever we have a directed edge in the tree going from label k to label k-1, then this edge essentially becomes an arc of the quadrangulation. We show that the edge oriented in the other direction, called say e, induces three further arcs of a quadrangle. So e goes from label k-1 to k. Consider the corners before and following e in the contour exploration, which is a corner around the vertex with label k. The successor of the corner after e is a corner with label k-1, and this has a successor with label k-2. By construction, this must also be the successor of the corner before e. Why? Well as we traverse the contour beyond e, the first appearance of label k-1 must happen before the first appearance of label k-2, as the increments can only be in {-1,0,1}. This gives us the three further arcs. Note also that the 2-colouring of the quadrangulation is given by the parity of the tree-labelling.

I was bothered about what happens if two vertices with label k-1 are in fact the same. This would happen if, for example, the vertex labelled k is a leaf. Then, at least two of the corners around the single vertex with label k-1 have the same corner as successor. A naïve attempt at drawing the resulting arcs did not give a quadrangle. The key observation is that you have to draw the arcs in the direction of the contour process. So in this case, the arc from the corner before edge e will loop all the way around the vertex with label k, so it contains the other two relevant arcs on its way to the vertex with label k-2, giving us the ‘pacman’ quadrangle discussed earlier.

The other case we have to check is when our base edge joins two vertices with label k. Then the other two vertices of the face will have label k-1. This is similar to the above, and slightly easier.

As a preliminary to checking that we can invert this construction, we observe that the vertices of the quadrangulation are the vertices of the original tree plus $v_*$ , and furthermore, the labels in the tree are given by the graph distance from $v_*$ in the quadrangulation, with a constant added uniformly so that the root vertex has label 0.

At this point, we observe that in the construction, we didn’t specify how to choose the rooted edge of the quadrangulation. Canonically, we take it to be the arc between the first corner of the root in the contour process, and its successor. However, we can orient it in either direction, giving us the extra factor of 2 we were looking for.

Returning to the inverse, it is clear what to do when we see a quadrangle corresponding to the second case above – namely put an edge between the two vertices with label k. In the case where the face has labels {k,k-1,k-1,k-2} it is less obvious. Note though that by starting at the first corner of the root, which is identified by the rooted edge in the quadrangulation, we can recover the contour process from the arcs of the quadrangulation, and the labels. So when we see such a face, we can use this information to choose which of the (k-1)-labelled vertices to join to the vertex with label k.

Anyway, now we are convinced that this bijection works, the next stage is to apply it to gain extra information about a uniformly-chosen large quadrangulation. We can view the vertices as being those of a large uniform plane tree, and the labels as given by a random walk along this large tree. We might expect to see this labelling structure converge to something that looks like Brownian motion indexed by a Brownian continuum random tree, in a sense to be made more precise. And the labelling is not merely a decoration in the quadrangulation, since it specifies the distance to the identified point $v_*$ . In particular, this gives a bound on the distance between any two vertices in the quadrangulation, eg two vertices chosen uniformly at random. In fact, by looking more carefully at the scaling limit of the uniform tree’s contour process, we can say rather more than that.

Random Maps 1 – Towards the Schaeffer Bijection

Posted on July 29, 2014 by dominicyeo

I have spent the past ten days in Saint Flour, an inaccessible but picturesque town in the rolling hills of Cantal, in the middle of France, and venue for perhaps the most notable summer school in probability. My highlight has been the course ‘Aspects of Random Maps’ delivered by Gregory Miermont, and I thought I should write a few posts about points of interest encountered during the lectures and private study.

A map is an embedding of a connected graph onto a surface. We typically do not care about the nature of this embedding up to homeomorphisms of the surface which preserve orientations of the map. One advantage for doing this is that the set of maps now might be countable, and the set of maps with n edges might be finite. This can be proved by considering a map to be obtained by glueing together polygonal faces. Some potential glueings are impossible, and some are equivalent, but for a fixed number of edges, the number of such sets of polygons and a possible glueing is finite. In fact we can be much more precise than this about how to describe precisely the legal glueing through a triple of permutations, but I won’t discuss this here.

I haven’t yet given a complete definition of a map. We want a typical large map, that is a map with a large number of vertices and edges, to be topologically roughly the same as the surface it is embedded into. In particular, the map needs to encode the geometric features of the surface. So a small triangle on the surface of a torus should not be considered a map. To rigorise this, we demand that any face of a map should be a topological disc, in particular, it should be simply connected. Since the torus itself is not simply connected, this excludes our triangle example. Note a single vertex on a torus is also excluded.

Although it goes against the usual order of definitions, it might be helpful to think of a map as an embedding which satisfies Euler’s formula: V – E + F = 2 -2g, where g is the genus of the surface. For a connected planar graph, induction is on the number of edges and vertices is the typical way to prove this result. The inductive step works the same on a more general surface, but it is less clear what the base case should be. Another consequence of the definition is that we should work on the sphere rather than the plane. From now on, this is our surface of interest.

We begin by considering $\mathcal{M}_n$ to be the family of rooted plane maps with n edges. The root is a distinguished oriented edge. Our aim is to count the size of this set.

Before doing this, we digress onto the topic of rooted plane trees. Note that any (rooted) tree in the classical sense is planar, but in a rooted plane tree, we also specify the geometric ordering of the offspring. For example, if the root has two offspring, of which one has precisely one offspring and the other has none, we consider these as two separate cases.

So now, if we denote by $a_k$ the number of plane trees with k edges, we can define a generating function via $A(z):=\sum_{k\ge 0} a_k z^k$ . If the root vertex v has no offspring, this gives one possibility corresponding to k=0. Otherwise, there is a well-defined left-most offspring of the root, called u. Then u and its descendents form a plane tree, and v and its descendents apart from those through u also form a plane tree. So after accounting for the edge between u and v, we obtain

$A(z)=1+zA(z)^2,$

whenever A(z) is defined. We now can apply whichever is our favourite method of showing that this is the generating function of the Catalan numbers, $a_k=\frac{1}{k+1}\binom{2k}{k}$ .

There is a more complicated version of this generating function argument due to Tutte that allows us to enumerate $\mathcal{M}_n$ . It is convenient to work with a second variable in the generating function that encodes the degree of the root face. The resulting equation of generating functions is less well-known but using the Lagrange inversion formula gives the explicit expression

$|\mathcal{M}_n|=\frac{2}{n+2}\cdot \frac{3^n}{n+1}\binom{2n}{n}.$

Although there are extra terms, this motivates seeking a bijection between maps, and some version of rooted plane trees, perhaps decorated with some extra information. As in many cases, this will turn out to be possible. The bijection we end up with will not just help us enumerate the maps, but will also allow us to control a lot more information about distances in the map, which will be particularly useful when we try to take limits.

The first observation is that given a map, we can construct a dual map, by placing fresh vertices somewhere in the middle of each face, and joining a pair of these if the corresponding faces in the original graph share an edge.

Alternatively, we can place the same fresh vertices in the middle of each face, then join each new vertex to an original vertex, if that original vertex lies on the face corresponding to the new vertex. If you focus in on an original edge, it is clear that it is now surrounded by a ‘diamond’ (if you’ve drawn the diagram in a natural way) of new edges. Removing the original edges thus leaves us with a quadrangulation. This procedure is called the ‘trivial bijection’ between $\mathcal{M}_n$ and $\mathcal{Q}_n$ , the family of rooted quadrangulations with n faces. Note that the root in such a quadrangulation is an identified directed edge, rather than a vertex. We haven’t yet specified how to describe the root of the resulting quadrangulation. It suffices to take the first new edge which lies clockwise of the root edge in the original graph, seen from the ‘tail’ of the root, which is of course oriented.

In this, and the bijections which follow, the natural questions to ask are: a) is the inverse obvious? and b) what happens to self-loops and isthmuses? Here, the inverse really is obvious. Any quadrangulation is bipartite, hence two-colourable, so we need to fix one colour and join the two vertices of that colour within each face to recover the original graph. The root tells us which colour we need to take. As for the second question, first we should say that an isthmus is an edge which has the same face on both sides. This causes no problems in this particular bijection. For the self-loops, we get a sort of Pacman-like quadrangle, with two ‘outer-edges’ between the same two vertices, and an edge between one of the outer vertices and some internal vertex. This edge contributes twice to the degree of the face.

The upshot of this is that for a simple enumeration, it suffices to prove that $|\mathcal{Q}_n|=\frac{2}{n+2}\cdot \frac{3^n}{n+1}\binom{2n}{n}$ . This may not look like we have achieved much, but we can now apply Euler’s formula to any quadrangulation in this set to deduce that the number of vertices present is n+2. If we consider the set $\mathcal{Q}_n^*$ , where now we identify a particular vertex $v_*$ in the quadrangulation, it suffices to prove that $|\mathcal{Q}_n^*|=2.3^n \cdot a_n$ , where $a_n$ is the nth Catalan number as before. Now we have the most efficient setup to look for a bijection with some type of decorated plane tree as discussed before.