A bijection for rooted maps on general surfaces
(extended abstract)

Guillaume Chapuy, Maciej Dolęga

► To cite this version:

Guillaume Chapuy, Maciej Dolęga. A bijection for rooted maps on general surfaces (extended abstract). 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.181-192, 10.46298/dmtcs.2536 . hal-01337829

HAL Id: hal-01337829

https://hal.science/hal-01337829

Submitted on 27 Jun 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A bijection for rooted maps on general surfaces (extended abstract)

Guillaume Chapuy$^{1†}$ and Maciej Dołęga$^{2‡}$

$^{1,2}$LIAFA, Université Paris 7, Case 7014, 75205 Paris Cedex 13, France

$^{2}$Instytut Matematyczny, Uniwersytet Wrocławski, pl. Grunwaldzki 2/4, 50-384 Wrocław, Poland

**Abstract.** We extend the Marcus-Schaeffer bijection between *orientable* rooted bipartite quadrangulations (equivalently: rooted maps) and *orientable* labeled one-face maps to the case of all surfaces, orientable or non-orientable. This general construction requires new ideas and is more delicate than the special orientable case, but carries the same information. It thus gives a uniform combinatorial interpretation of the counting exponent $\frac{5(h-1)}{2}$ for both orientable and non-orientable maps of Euler characteristic $2 - 2h$ and of the algebraicity of their generating functions. It also shows the universality of the renormalization factor $n^{1/4}$ for the metric of maps, on all surfaces: the renormalized profile and radius in a uniform random pointed bipartite quadrangulation of size $n$ on any fixed surface converge in distribution. Finally, it also opens the way to the study of Brownian surfaces for any compact 2-dimensional manifold.

**Résumé.** Nous étendons la bijection de Marcus et Schaeffer entre quadrangulations biparties *orientables* (de manière équivalente: cartes enracinées) et cartes à une face étiquetées *orientables à toutes* les surfaces, orientables ou non. Cette construction générale requiert des idées nouvelles et est plus délicate que dans le cas particulier orientable, mais permet des utilisations similaires. Elle donne donc une interprétation combinatoire uniforme de l'exposant de comptage $\frac{5(h-1)}{2}$ pour les cartes orientables et non-orientables de caractéristique d'Euler 2 – 2$h$, et de l'algébricité des fonctions génératrices. Elle montre l'universalité du facteur de normalisation $n^{1/4}$ pour la métrique des cartes, sur toutes les surfaces: le profil et le rayon d'une quadrangulation enracinée pointée sur une surface fixée converge en distribution. Enfin, elle ouvre à la voie à l'étude des surfaces Browniennes pour toute 2-variété compacte.

**Keywords:** Graphs on surfaces, trees, random discrete surfaces

This paper is an extended abstract of [7], which will be submitted elsewhere.

## 1 Introduction

*Maps* (a.k.a. ribbon graphs, or embedded graphs) are combinatorial structures that describe the embedding of a graph in a surface (see Section 2 for precise definitions). These objects have received much attention from many different viewpoints, because of their deep connections with various branches of discrete mathematics, algebra, or physics (see e.g. [13, 11] and references therein). In particular, maps have

<footnote>†Acknowledge partial support from Agence Nationale de la Recherche, grant ANR 12-JS02-001-01 "Cartaplus" and partial support from Ville de Paris, grant "Émergences 2013, Combinatoire à Paris".</footnote>

<footnote>‡Acknowledge support from Agence Nationale de la Recherche, grant ANR 12-JS02-001-01 "Cartaplus".</footnote>
remarkable enumerative properties, and the enumeration of maps (either by generating functions, matrix integral techniques, algebraic combinatorics, or bijective methods) is now a well established domain on its own. The reader may consult [1, 3] for entry points into this fast-growing literature. This paper is devoted to the extension of the bijective method of map enumeration to the case of all general surfaces, and to its first consequences in terms of combinatorial enumeration and probabilistic results.

**Orientable surfaces.** Let us first recall briefly the situation in the orientable case. A fundamental result of Bender and Canfield [2], obtained with generating functions, says that the number $m_g(n)$ of rooted maps with $n$ edges on the orientable surface of genus $g \ge 0$ (obtained by adding $g$ handles to a sphere, see Section 2) is asymptotically equivalent to

$$m_g(n) \sim t_g n^{\frac{5(g-1)}{2}} 12^n, \quad n \to \infty, \qquad (1)$$

for some $t_g > 0$. In the planar case ($g = 0$) this follows from the exact formula $m_0(n) = \frac{2 \cdot 3^n (2n)!}{(n+2)! n!}$ due to Tutte [20], whose combinatorial interpretation was given by Cori-Vauquelin [10] and much improved by Schaeffer [19]. The bijective enumerative theory of planar maps has since grown into a domain of research of its own, out of the scope of this introduction; consult [1, 3] and references therein. For general $g$, the combinatorial interpretation of Formula (1), and in particular of the counting exponent $\frac{5(g-1)}{2}$, was given in [16, 8], thanks to an extension of the Cori-Vauquelin-Schaeffer bijection to the case of higher genus surfaces. The bijection of [16, 8] associates maps on a surface with labeled one-face maps on the same surface. The latter have a much simpler combinatorial structure and can be enumerated by elementary methods. Moreover, the bijective toolbox was proven to be relatively flexible, and enabled to prove formulas similar to (1) for many different families of orientable maps [6], extending results previously obtained by generating functions [12].

Beyond the combinatorial interpretation of counting formulas, an important motivation for developing the bijective methods is that they are the cornerstone of the study of random maps. In the planar case, Schaeffer's bijection was the starting point of the study of random planar maps [9]. The field has now much developed, culminating with the proof by Le Gall [15] and Miermont [17] that uniform random quadrangulations as metric spaces, rescaled by $n^{1/4}$, converge in distribution to some random metric space called *Brownian Map*. For higher genus surfaces, Bettinelli used the Marcus-Schaeffer bijection [16, 8] to prove the existence of scaling limits for uniform quadrangulations of fixed genus, rescaled by the same exponent $n^{1/4}$, and study some of their properties [4].

**Non-orientable surfaces and main results.** From the viewpoint of generating functions, orientable and non-orientable surfaces are not very different. Indeed, in the paper previously mentioned [2], Bender and Canfield also showed, by the same method, that the number of rooted maps with $n$ edges on the non-orientable surface of type $h \ge \frac{1}{2}$ (obtained by adding $2h$ crosscaps to a sphere, see Section 2; here $h$ is either an integer or a half-integer) is asymptotically equivalent to

$$\tilde{m}_h(n) \sim p_h n^{\frac{5(h-1)}{2}} 12^n, \quad n \to \infty, \qquad (2)$$

for some $p_h > 0$. However, from the viewpoint of bijective methods, the orientable and non-orientable situations are very different: indeed, all the existing bijections for maps (including the ones of [16, 8]) crucially use the existence of a global orientation of the surface as a starting point of their construction. In particular, the existing literature says nothing about random maps on non-orientable surfaces since it lacks the bijective tools to study them.
The main achievement of this paper is to bridge this gap. We are able to drop an assumption of the orientability in Marcus-Schaeffer construction [16, 8] and hence extend it to the case of *all* surfaces (orientable or non-orientable): for any surface $\mathcal{S}$ there is a bijection between rooted maps on $\mathcal{S}$ (more precisely, rooted bipartite quadrangulations) and labeled one-face maps on $\mathcal{S}$. This is done at the cost of using only a *local* orientation in the construction instead of a *global* one: the local rules of the bijection are the same as in the Marcus-Schaeffer bijection, but the local orientation is recursively constructed in a careful way so that in the orientable case it is consistent with the global orientation. In particular, the correspondence between *distances* in the quadrangulation and *labels* in the one-face map is preserved. As a consequence, not only does the bijection lead to a *uniform combinatorial interpretation* of both the orientable (1) and non-orientable (2) counting formulas, but it also enables to study distances in uniform random maps on a fixed surface. In particular we show that an exponent $n^{1/4}$ is *universal* for *all* maps in the following sense: the profile and radius of a uniform random bipartite quadrangulation of size $n$ on a fixed surface converge in distribution, after renormalization by $n^{1/4}$.

Our bijection thus opens the way to the study of *scaling limits* of maps on *all* surfaces for the Gromov-Hausdorff topology – analogous to the project initiated in [4] for the orientable case. In the forthcoming paper [5], the following result is proved: for any surface $\mathcal{S}$, random uniform bipartite quadrangulations with $n$ faces on $\mathcal{S}$ converge, up to subsequence extraction and proper renormalization, to a random metric space $\mathcal{S}_{\text{Brownian}}$ that is almost surely homeomorphic to $\mathcal{S}$ and has Hausdorff dimension 4. The proof of this result heavily relies on the bijection of the present paper. Much work remains to be done on the subject (such as removing the subsequence extraction), and the bijection of the present paper should play an important role in it.

**Structure of this extended abstract.** Section 2 sets up basic notation and definitions. Section 3 states the main result, and describes the main bijection. We give a full description of the construction, but we unfortunately have to omit part of the proof that it is well defined, as well as the full description of the converse bijection. See [7] for a full account, with proofs, that takes about 15 pages more. Section 4 investigates the consequences of the bijection from the asymptotic and probabilistic viewpoint, and gathers final comments.

**Acknowledgments.** G.C. thanks Gilles Schaeffer for mentioning the problem to him, back in 2007.

# 2 Surfaces, maps, and quadrangulations

## 2.1 Surfaces, graphs, and maps

A *surface* is a compact, connected, 2-dimensional manifold. We consider surfaces up to homeomorphism. Denote $\mathbb{N} = \{0, 1, 2, 3, \dots\}$ and $\frac{1}{2}\mathbb{N} = \{0, \frac{1}{2}, 1, \frac{3}{2}, \dots\}$. For any $h \in \mathbb{N}$, we denote by $S_h$ the torus of genus $h$, that is, the *orientable* surface obtained by adding $h$ *handles* to the sphere. For any $h \in \frac{1}{2}\mathbb{N} \setminus \{0\}$, we denote by $N_h$ the *non-orientable* surface obtained by adding $2h$ *cross-caps* to the sphere. Hence, $S_0$ is the sphere, $S_1$ is the torus, $N_{1/2}$ is the projective plane and $N_1$ is the Klein bottle. The *type* of the surface $S_h$ or $N_h$ is the number $h$. By the theorem of classification, each orientable surface is homeomorphic to one of the $S_h$ and each non-orientable surface is homeomorphic to one of the $N_h$ (see e.g. [18]).

Our *graphs* are finite and undirected; loops and multiple edges are allowed. A *map* is an embedding (without edge-crossings) of a connected graph into a surface, in such a way that the *faces* (connected components of the complement of the graph) are simply connected. Maps are always considered up to homeomorphism. A map is *unicellular* if it has a single face. Unicellular maps are also called *one-face maps*. We will call a map *orientable* if the underlying surface is orientable; otherwise we will call it
non-orientable. Each edge in a map is made of two *half-edges*, obtained by removing its middle-point. The *degree of a vertex* is the number of incident half-edges. A *corner* in a map is an angular sector determined by a vertex, and two half-edges which are consecutive around it. The *degree of a face* is the number of edges incident to it, with the convention that an edge incident to the same face on both sides counts for two. Equivalently, the degree of a face is the number of corners lying in that face. Note that the total number of corners in a map equals the number of half-edges, and also equals twice the number of edges. A map is *rooted* if it is equipped with a distinguished half-edge called the *root*, together with a distinguished side of this half-edge. The vertex incident to the root is the *root vertex*. The unique corner incident to the root half-edge and its distinguished side is the *root corner*. On pictures, we will represent rooted maps by shading the root corner and by indicating the side of the root half-edge that is incident to it. *From now on, all maps are rooted.*

The type $h(M)$ of a map $M$ is the type of the underlying surface, that is to say, the Euler characteristic of the surface is $2 - 2h(M)$. If $M$ is a map, we let $V(M)$, $E(M)$ and $F(M)$ be its sets of vertices, edges and faces. Their cardinalities $v(M)$, $e(M)$ and $f(M)$ satisfy the Euler formula:

$$e(M) = v(M) + f(M) - 2 + 2h(M). \qquad (3)$$

## 2.2 Representation of a unicellular map

Since by definition the unique face of a unicellular map is simply connected, cutting the surface along the edges of a unicellular map with $n$ edges gives rise to a polygon with $2n$ edge-sides (a $2n$-gon). This polygon inherits a root corner from the map, and can be oriented thanks to the distinguished side of the root half-edge. Conversely, any unicellular map can be obtained from a rooted oriented $2n$-gon, by gluing edge-sides of the polygon by pairs. It is important to note that given two edge-sides of a polygon, there are two ways of gluing them together: we say that a gluing is *straight* if the identification of the edge-sides gives a topological cylinder, and that it is *twisted* if the identification gives a Möbius strip. The set of the straight (twisted, respectively) edges of a unicellular map $M$ will be denoted by $E_s(M)$ ($E_t(M)$, respectively). It is easy to see that $M$ is orientable iff $E_t(M) = \emptyset$.

Moreover, given a unicellular map $M$, if we number the sides of the corresponding $2n$-gon from 1 to $2n$ starting from the root corner and following its orientation, then $M$ naturally induces a *matching* of the set $[2n] := \{1, 2, \dots, 2n\}$ (two edge-sides of the $2n$-gon are matched if and only if they are glued together). Clearly, the knowledge of that matching and of the set of gluings that are twisted or straight, is enough to reconstruct the polygon gluing, hence the map. Consequently, there is a one-to-one correspondence between unicellular maps with $n$ edges and pairs of *matchings* $\mathcal{P}(E_s(M)), \mathcal{P}(E_t(M))$ having disjoint support and whose union is a perfect matching of $[2n]$. See Fig. 1 for an illustration.

## 2.3 Maps and bipartite quadrangulations

A *quadrangulation* is a map having all faces of degree 4. A map is *bipartite* if its vertices can be colored in two colors in such a way that adjacent vertices have different colors (say black and white). By convention the color of the root vertex of a rooted bipartite map is always taken to be black.

A standard result, that goes back to Tutte, asserts that for all $n, v, f \ge 1$ and any surface $S$ (orientable or not), there is a bijection between rooted maps on $S$ with $n$ edges, $v$ vertices and $f$ faces, and rooted bipartite quadrangulations on $S$ with $n$ faces, $v$ black and $f$ white vertices (and $2n$ edges).

This result is based on a classical construction that we briefly recall. Given a map $M$ with black vertices, add a new (white) vertex inside each face of $M$, and link it by a new edge to all the corners
<figure><img src="image_2.png" /><figcaption>Fig. 1: (A) A unicellular map drawn on a Klein bottle $N_1$ (opposite sides of the dotted rectangle should be glued together as indicated by arrows); (B) The same map represented as a polygon with glued sides (straight and twisted gluings are indicated by plain and dotted lines, respectively). The corresponding sets of matchings are $E_s(M) = \{\{1, 30\}, \{2, 29\}, \{3, 14\}, \{18, 27\}, \{23, 24\}, \{22, 21\}, \{16, 17\}, \{11, 12\}\}$, and $E_t(M) = \{\{13, 26\}, \{10, 25\}, \{9, 20\}, \{8, 19\}\}$.</figcaption></figure>

incident to that face. By construction, the map $q$ obtained by keeping all vertices, and only newly created edges, is a bipartite quadrangulation. Conversely, given a bipartite quadrangulation $q$, add a diagonal between the two black corners inside each face: then the set of black vertices, together with the added diagonal edges, forms a map whose associated quadrangulation is $q$.

This correspondence is the reason why, although we concentrate in the rest of this text on bipartite quadrangulations, our results have implications for all maps.

# 3 The bijection

## 3.1 Statement of the main result and overview of the construction

A unicellular map $\mathcal{M}$ is called *labeled* if its vertices are labeled by integers such that:

(1) the root vertex has label 1;

(2) if two vertices are linked by an edge, their labels differ by at most 1.

If in addition we have:

(3) all the vertex labels are positive

then the unicellular map is called *well-labeled*.

The main result of this paper is a construction of the bijection establishing the following result:

**Theorem 3.1** For each surface $\mathcal{S}$ and integer $n \ge 1$, there exists a bijection between the set of rooted bipartite quadrangulations on $\mathcal{S}$ with $n$ faces and the set of well-labeled unicellular maps on $\mathcal{S}$ with $n$ edges.
Moreover, if for a given bipartite quadrangulation we denote by $N_i$ the set of its vertices at distance $i$ from the root vertex, and by $E(N_i, N_{i-1})$ the set of edges between $N_i$ and $N_{i-1}$, then the associated well-labeled unicellular map has $|N_i|$ vertices of label $i$ and $|E(N_i, N_{i-1})|$ corners of label $i$.

As we will see, the above theorem easily implies the following variant, which turns out to be easier to use for enumerative purposes:

**Theorem 3.2** For each surface $\mathbb{S}$ and integer $n \ge 1$, there exists a 2-to-1 correspondence between the set of rooted bipartite quadrangulations on $\mathbb{S}$ with $n$ faces carrying a pointed vertex $v_0$, and labeled unicellular maps on $\mathbb{S}$ with $n$ edges.

Moreover, if for a given bipartite quadrangulation we denote by $N_i$ the set of its vertices at distance $i$ from the vertex $v_0$, and by $E(N_i, N_{i-1})$ the set of edges between $N_i$ and $N_{i-1}$, then the associated well-labeled unicellular map has $|N_i|$ vertices of label $i + \ell_{min} - 1$ and $|E(N_i, N_{i-1})|$ corners of label $i + \ell_{min} - 1$, where $\ell_{min}$ is the minimum vertex label in the unicellular map.

The full description of the construction leading to Theorem 3.1 proceeds in two steps. First, one has to construct what we call the dual exploration graph (DEG)$^{(i)}$, and then use it to construct the labeled unicellular map associated with a quadrangulation. Description of the construction of DEG for a given quadrangulation is the core of our bijection and it is explained in details in the next section (Section 3.2).

## 3.2 From quadrangulations to well-labeled unicellular maps

### 3.2.1 Constructing the dual exploration graph $\nabla(q)$

Let $q$ be a rooted quadrangulation on a surface, and $v_0$ be the root vertex of $q$. In this subsection we describe how to draw a directed graph $\nabla(q)$ on the same surface. To distinguish vertices, edges, etc. of the quadrangulation and of the new graph we will say that the vertices, edges, etc. of the graph $\nabla(q)$ are *blue*, while edges of $q$ are *black*. The construction goes in several steps, numbered from 0 to 3. Fig. 2 below should serve as a support for reading this subsection.

* **Step 0–a (Labeling).** We label the vertices of $q$ according to their distance from the root vertex $v_0$. Note that this also induces a labelling of corners (the label of a corner is the label of the unique vertex it is incident to). Since $q$ is bipartite, the extremities of each edge have labels of different parity. By the triangle inequality this implies that faces are either of type $(i-1, i, i-1, i)$ or of type $(i-1, i, i+1, i)$ for $i \ge 1$, where the type of a face is the sequence of its corner labels. An edge of $q$ whose extremities are labeled $i$ and $i+1$ is said to be of *label $i$*.

Our goal is to draw a blue graph in such a way that at the end of the construction, each edge of the quadrangulation $q$ is crossed by exactly one blue edge. We introduce some terminology: edges of $q$ that are not crossed by a blue edge are called *free*, and the *label* of a blue edge is the label of the unique edge of $q$ is crosses. We are going to construct the blue edges (and thus the graph $\nabla(q)$) by increasing label. We start by drawing edges of label 0:

* **Step 0–b (Initialization).** We add a new blue vertex in each corner labeled by 0 and we connect them by a cycle of blue edges around the pointed vertex $v_0$ as on Fig. 2. We orient this cycle in such a way that it is oriented from the root half-edge to the root corner. There is a unique vertex of the blue graph lying in the root corner of $q$, and this vertex has a unique corner that is separated from $v_0$ by the blue cycle.

<footnote>(i) A version of the DEG was already present as tool of proof in the orientable case [8, Fig. 5]. However, here this graph plays a crucial role not only in proofs, but in the construction itself.</footnote>
<figure><img src="image_3.png" /><figcaption>Fig. 2: The construction of $\nabla(q)$. Top: Step 0b; Bottom: the face $F$ and the edge $e$ selected by Step 1; Right: Step 2.</figcaption></figure>

We declare that corner to be the *last visited corner (LVC)* of the construction and we equip it with the
orientation inherited from the one of the cycle (the LVC will be dynamically updated in the sequel). We
set $i := 1$ and we continue.

We now proceed with the inductive part of the construction.

* **Step 1 (choosing where to start).** If there are no more free edges in $q$, we stop. Otherwise, we perform the tour of the blue graph, starting from the LVC. We stop as soon as we visit a face $F$ of $q$ having the following properties: $F$ is of type $(i-1, i, i+1, i)$, and $F$ has exactly one blue vertex already placed inside it. It is true, but not trivial, that such a face always exists [7, Proposition 3.3].

If the face $F$ is incident to only one free edge, we let $e$ be that edge. If not, let $u$ be the blue vertex already contained in the face $F$. Then $u$ is incident to two blue edges of label $(i-1)$, one incoming and one outgoing [7, Lemma 3.4]. We use these two oriented edges to define an orientation of $F$ by saying that they turn counterclockwise around the corner of label $(i-1)$. We then let $e$ be the first edge of label $i$ encountered clockwise around $F$ after that corner. One can sum up the choice of the edge $e$ with Fig. 2 (Bottom), that by [7, Lemma 3.4] covers all the possible cases.

* **Step 2 (attaching a new branch of blue edges labeled by i starting across e).** We draw a new blue vertex $v$ in the unique corner of $F$ delimited by $e$ and its neighboring edge of label $i-1$, and we let $a$ the vertex of $q$ incident to this corner. We now start drawing a path of directed blue edges starting from $v$ as follows: we cross $e$ with a blue edge leaving the face $F$, thus entering a face $F'$. If $F'$ contains a corner of label $(i-1)$, we attach the new blue edge to the blue vertex lying in that corner ([7, Lemma 3.4] ensures that this blue vertex exists). If not, then we continue recursively drawing a path of new blue vertices and new blue edges turning around $a$, as on Fig. 2, until we reach a face containing a corner of label $i-1$, and we finish by attaching the path to the blue vertex lying in that corner. We define the LVC as the corner
lying to the right of the last directed blue edge we have drawn, in the local orientation defined by the fact
that the path just drawn turns counterclockwise around a.

* Step 3 (induction). If there are no more free edges of label $i$ in $q$, we set $i := i + 1$, otherwise we let $i$ unchanged. We then go back to Step 1 and continue.

* Termination. We let $\nabla(q)$ be the blue embedded graph on $S$ obtained at the end of the construction.
See Fig. 3 for an example of the construction on the Klein bottle.

<figure><img src="image_4.png" /><figcaption>Fig. 3: Left: A rooted quadrangulation $q$ on the Klein bottle $N_1$. Right: The associated dual exploration graph $\nabla(q)$ is depicted in blue. To help the reader visualize the construction, we have numbered the blue edges appearing after Step 0 by $a, b, \dots, z$ in their order of appearance in the construction. We have not indicated the orientation of these edges, to make the picture lighter.</figcaption></figure>

It is not immediate from the construction above, but one can prove a following result:

**Proposition 3.3 ([7, Prop. 3.3., Lemma 3.4])** The construction of $\nabla(q)$ is well defined. Moreover, $\nabla(q)$ is formed by a unique oriented cycle encircling $v_0$, to which oriented trees are attached. After the construction of $\nabla(q)$ is complete, each face of $q$ is of one of the two types of Fig. 4-Left-Top, up to reflection and up to the orientation of blue edges, for some $i \ge 0$.

### 3.2.2 Constructing the well-labeled unicellular map $\Phi(q)$.

Let as before $q$ be a rooted quadrangulation on a surface $S$, and $v_0$ be its root vertex. We construct the dual exploration graph $\nabla(q)$ as in the previous subsection, and as before we call its edges *blue*. By Proposition 3.3, at the end of the construction, all the faces of $q$ are of one of the two types shown on Fig. 4-Left-Top. We now add one new, *red*, edge in each face of $q$ according to the rule of Fig. 4-Left-Bottom.

We let $\Phi(q)$ be the map on $S$ consisting of all the red edges, and of all the vertices of $q$ except $v_0$. We declare the root corner of $\Phi(q)$ to be the unique corner of label 1 of $\Phi(q)$ incident to the root edge of $q$, and we equip it with the local orientation inherited from the one of the root corner of $q$ along its root edge. Fig. 4 gives an example of the construction.

**Lemma 3.4** $\Phi(q)$ is a well-defined well-labeled unicellular map.
<figure><img src="image_5.png" /><figcaption>Fig. 4: Left-Top: face-types after the construction of $\nabla(q)$. Left-Bottom: constructing $\Phi(q)$ from $\nabla(q)$. Middle and Right: Construction (in red) of the labeled unicellular map $\Phi(q)$ associated to the bipartite quadrangulation from Fig. 3.</figcaption></figure>

**Proof:** We first notice that $H = S \setminus \Phi(q)$ is homeomorphic to a disk. Indeed, since the dual exploration graph $\nabla(q)$ goes through any face of $H$, it is easy to see that any loop in $H$ can be retracted to a point along the tree-like structure of $\nabla(q)$ guaranteed by Proposition 3.3. This proves at the same time that $\Phi(q)$ is connected, that it is a valid map on $S$, and that it has only one face.

It remains to check that the labeling of vertices makes $\Phi(q)$ a valid well-labeled unicellular map. First, it is clear by construction that the label of the root vertex is 1, and that all labels in $\Phi(q)$ are at least 1. Moreover, by construction, and more precisely by the rules of Fig. 4—Left-Bottom, any two vertices of $\Phi(q)$ that are linked by an edge have labels differing by $\pm 1$ or 0, so there is nothing more to prove. $\square$

Unfortunately, we do not have space in this extended abstract to describe the reverse bijection of $\Phi$, and even less to prove that $\Phi$ is indeed a bijection. In a few words, given a unicellular map, there is a recursive way to reconstruct the edges of the associated quadrangulation by increasing label, and to reconstruct at the same time an associated blue graph, in such a way that the local rules use only the one-neighborhood of the already constructed blue graph, and yet ensure that this blue graph will coincide with DEG of the full quadrangulation at the end of the construction. The construction is a bit long, and we refer to [7, Sections 3.3–3.4] for a proof of the following fact:

**Theorem 3.5** The mapping $\Phi$ realizes the bijection announced in Theorem 3.1

We now briefly explain how to deduce Theorem 3.2 from Theorem 3.1. Let $q$ be a rooted bipartite quadrangulation and let $v_0$ be a pointed vertex of $q$. Let us choose a corner $\rho(q, v_0)$ of $q$ incident to $v_0$. In general, there are several ways to choose this corner, and a simultaneous choice of the corner $\rho(q, v_0)$ for all $q$ and $v_0$ is called an *oracle*. Given an oracle, we can consider the *rerooted quadrangulation* $q'$ obtained by declaring that $\rho(q, v_0)$ is the root corner of $q'$. This quadrangulation is equipped with an additional marked corner (the original root corner of $q$). We can then apply the bijection $\Phi$ to $q'$ and we obtain a well-labeled unicellular map $M$. Since $M$ has 2n corners and $q'$ has 4n corners, we can use the marked corner of $q'$ to mark a corner of $M$ and to get an additional sign $\epsilon \in \{+, -\}$ (for example choose
the marked corner to be the corner of $\mathcal{M}$ incident to the root edge $e$ of $q$, and choose $\epsilon$ according to which extremity of $e$ has the greatest distance to $v_0$ in $q$). We declare this corner to be the new root of $\mathcal{M}$, and we now shift all the labels of $\mathcal{M}$ by the same integer, in such a way that this corner receives the label 1. We thus have obtained a labeled unicellular map $\mathcal{M}'$ that carries a marked oriented corner $c$ of minimum label (the root corner of $\mathcal{M}$), together with a sign $\epsilon$, and we denote by $\Lambda_{\rho}(q, v_0) := (\mathcal{M}', \epsilon)$.

One can prove that the two sources of multiplicity in this construction (on the one hand, the number of choices for the oracle; on the other hand, the fact that we obtain a labeled unicellular map with a marked corner of minimum label) exactly compensate each other. We refer to [7, Theorem 3.11] for a precise statement of that fact, and for a standard argument involving Hall's perfect matching theorem that enables to deduce Theorem 3.1 from Theorem 3.2 in the following more precise form:

**Theorem 3.6** For each $n \ge 1$ and each surface $\mathcal{S}$, there exists a choice of the oracle $\rho$ that makes $\Lambda_{\rho}$ a bijection between the set of rooted bipartite quadrangulations on $\mathcal{S}$ with $n$ faces and a marked vertex $v_0$, and the set of rooted labeled unicellular maps on $\mathcal{S}$ with $n$ edges equipped with a sign $\epsilon \in \{+, -\}$.

# 4 Enumerative and probabilistic consequences

## 4.1 Enumeration

The first consequence of the bijection given in this paper is the combinatorial interpretation of the algebraicity of map generating functions, and more precisely of their rationality in terms of some parameters. The bijection being established, the situation is totally similar to [8], whose enumerative sections could be copied here almost verbatim, see [7] for details. In particular, we obtain the following theorem:

**Theorem 4.1 (Combinatorial interpretation of the structure of map generating functions)** Let $\mathcal{S}$ be a surface of type $h$, and let $\vec{q}_{\mathcal{S}}(n)/\vec{q}_{\mathcal{S},\bullet}(n)$ be the number of (rooted maps)/(rooted maps pointed at a vertex or face) on $\mathcal{S}$ with $n$ edges (equivalently, (rooted quadrangulations)/(rooted quadrangulations pointed at a vertex) with $n$ faces). Let

$$Q_{\mathcal{S}}(t) := \sum_{n \ge 0} \vec{q}_{\mathcal{S},\bullet} t^n = \sum_{n \ge 0} (n + 2 - 2h) \vec{q}_{\mathcal{S}}(n) t^n$$

be the generating function of rooted maps pointed at a vertex or a face, by the number of edges. Moreover let $U \equiv U(t)$ and $T \equiv T(t)$ be the two formal power series defined by: $T = 1 + 3tT^2$, $U = tT^2(1 + U + U^2)$. Then $Q_{\mathcal{S}}(t)$ is a rational function in $U$.

Similarly as in the orientable case [8], the main singularity of $Q_{\mathcal{S}}(t)$ is easily understood combinatorially, from which we obtain a combinatorial interpretation of a famous result of Bender and Canfield [2]:

**Theorem 4.2** For each $h \in \{\frac{1}{2}, 1, \frac{3}{2}, 2, \dots\}$, there exists a constant $p_h$ such that the number of rooted maps with $n$ edges on the non-orientable surface of type $h$ satisfies:

$$\vec{q}_h(n) \sim p_h n^{\frac{5}{2}(h-1)} 12^n.$$

**Remark 1** In order to be able to perform the enumeration of labeled one-face maps combinatorially, it is crucial to remove the positivity condition of labels (i.e., to use Theorem 3.2 rather than Theorem 3.1). Because of this, we still cannot give a direct combinatorial proof that the series of rooted maps (without pointing) is algebraic. However, this is known to be the case from the generating function approach [2]. Note that the same remark applies to the orientable case treated in [8].
To give to the reader an idea of how to apply our bijection, we now present a very special case of the enumeration, namely the bijective counting of maps on the projective plane. We leave the reader check that the following result is equivalent to the generating function expression computed in [2].

**Corollary 4.3 (Bijective counting of maps on the projective plane)** *The number of rooted maps with n edges on the projective plane is equal to:*

$$ \frac{n}{n+1} \sum_{k \ge 1} \frac{4b_k}{n+k} \binom{2n-1}{n-k} 3^{n-k}, $$

where $b_k = \sum_{a+2b=k} \binom{k}{a,b,b}$.

**Proof:** In the case of the projective plane, unicellular maps have a simple structure: a single cycle (whose neighborhood on the surface forms a Möbius strip), with plane trees attached to it. These objects are easily enumerated by hand as follows. Call *bridge* a lattice walk on $\mathbb{Z}$ starting at 0, ending at 0, and taking steps in $\{0, -1, +1\}$. Then, clearly, the number $b_k$ given in the statement of the theorem is the number of bridges with $k$ steps. We claim that all labeled unicellular maps with $n$ edges on the projective plane can be constructed as follows. First, choose a bridge of size $k$ for some $k \ge 1$, close it in order to form a cycle of length $k$ with a marked vertex of label 0, and embed this cycle in the projective plane so that its neighborhood forms a Möbius strip. Now, attach a labeled plane tree on each of the $2k$ corners of this map in order to have $n$ edges in total. The number of ways to do that is the number of plane forests with $n-k$ edges and $2k$ components, which is $\frac{2k}{n+k} \binom{2n-1}{n-k}$, times $3^{n-k}$ to choose the label variations along each edge of the forest. Finally, there are $2n$ ways to choose a root corner in such a map, and 2 ways to choose its orientation. This gives a factor of $4n$ that has to be compensated by a factor of $1/(4k)$ that accounts for the fact that the cycle we started from is equipped with a marked (and oriented) position, thus leading to the total contribution of $\sum_k \frac{2nb_k}{n+k} \binom{2n-1}{n-k}$. By Theorem 3.2, we multiply this number by 2 to get the number of rooted quadrangulations with $n$ faces on $N_{1/2}$ pointed at a vertex. Since such a quadrangulation has $n+1$ vertices, we finally divide the result by $n+1$ to get the number we want. $\square$

## 4.2 Distances in random quadrangulations

Let $\mathcal{M}$ be a map and $v \in V(\mathcal{M})$. We define the *radius* of a map $\mathcal{M}$ centered at $v$ by the quantity

$$ R(\mathcal{M}, v) = \max_{u \in V(\mathcal{M})} d_{\mathcal{M}}(v, u). $$

For any $r > 0$, we also define the *profile of distances* from the distinguished point $v$:

$$ I_{(\mathcal{M}, v)}(r) = \#\{u \in V(\mathcal{M}) : d_{\mathcal{M}}(v, u) = r\}. $$

As a consequence of our bijection (using the now standard machinery developed by [9, 14, 4]), we have:

**Theorem 4.4** Let $q_n$ be uniformly distributed over the set of rooted, bipartite quadrangulations with $n$ faces on surface $S$, and let $v_0, v_1$ be two independent uniformly chosen vertices of $q_n$. Then the random variables

$$ \frac{1}{n^{1/4}} R(q_n, v_0), \frac{1}{n^{1/4}} d_{q_n}(v_0, v_1)), \left( \frac{n^{1/4}}{n+2-2h} I_{(q_n, v_0)} (\lfloor tn^{1/4} \rfloor) \right)_{t \in \mathbb{R}}, $$

converge in distribution.
We refer to [7] for a more precise statement, indicating in particular under which topologies the above limits are taken, and describing the limits in terms of a continuous stochastic process. As for the proofs, once again, given our main bijection, they are totally similar to the orientable case treated in [4], see [7]. **Final comment.** Our bijection satisfies an important property: namely, an analogue of the “distance bounding lemma” well known in the orientable case (see, e.g., [4, Eq. (3)]) is also valid in our setting (see [7, Lemma 3.9]). This property is the crucial point that opens the way to the study of scaling limits of maps on non-orientable surfaces, to be addressed in the forthcoming paper [5].

## References

[1] M. Albenque and D. Poulalhon. A generic method for bijections between blossoming trees and planar maps. arXiv:1305.1312, 2013.

[2] E. A. Bender and E. R. Canfield. The asymptotic number of rooted maps on a surface. *J. Combin. Theory Ser. A*, **43**(2):244–257, 1986.

[3] O. Bernardi and É. Fusy. Unified bijections for maps with prescribed degrees and girth. *J. Combin. Theory Ser. A*, **119**(6):1351–1387, 2012.

[4] J. Bettinelli. Scaling limits for random quadrangulations of positive genus. *Electron. J. Probab.*, **15**:no. 52, 1594–1644, 2010.

[5] J. Bettinelli, G. Chapuy, and M. Dołega. Non-orientable Brownian surfaces. In preparation.

[6] G. Chapuy. Asymptotic enumeration of constellations and related families of maps on orientable surfaces. *Combin. Probab. Comput.*, **18**(4):477–516, 2009.

[7] G. Chapuy and M. Dołega. A bijection for rooted maps on general surfaces. arXiv:1501.06942, 2015.

[8] G. Chapuy, M. Marcus, and G. Schaeffer. A bijection for rooted maps on orientable surfaces. *SIAM Journal on Discrete Mathematics*, **23**(3):1587–1611, 2009.

[9] P. Chassaing and G. Schaeffer. Random planar lattices and integrated superBrownian excursion. *Probab. Theory Related Fields*, **128**(2):161–212, 2004.

[10] R. Cori and B. Vauquelin. Planar maps are well labeled trees. *Canad. J. Math.*, **33**(5):1023–1042, 1981.

[11] B. Eynard. *Counting Surfaces*. Book in preparation, available on the author's webpage.

[12] Z. Gao. The number of degree restricted maps on general surfaces. *Discrete Math.*, **123**(1-3):47–63, 1993.

[13] S. K. Lando and A. K. Zvonkin. *Graphs on surfaces and their applications*, volume 141 of *Encyclopaedia of Mathematical Sciences*. Springer-Verlag, Berlin, 2004. With an appendix by Don B. Zagier.

[14] J.-F. Le Gall. A conditional limit theorem for tree-indexed random walk. *Stochastic processes and their applications*, **116**(4):539–567, 2006.

[15] J.-F. Le Gall. Uniqueness and universality of the Brownian map. *Ann. Probab.*, **41**(4):2880–2960, 2013.

[16] M. Marcus and G. Schaeffer. Une bijection simple pour les cartes orientables. *manuscript*, 2001.

[17] G. Miermont. The Brownian map is the scaling limit of uniform random plane quadrangulations. *Acta Math.*, **210**(2):319–401, 2013.

[18] B. Mohar and C. Thomassen. *Graphs on surfaces*, volume 2. Johns Hopkins University Press Baltimore, 2001.

[19] G. Schaeffer. *Conjugaison d'arbres et cartes combinatoires aléatoires*. Thèse de doctorat, Université Bordeaux I, 1999.

[20] W. T. Tutte. A census of planar maps. *Canad. J. Math.*, **15**:249–271, 1963.