Project topics and materials
Get Complete Project Material File(s) Now! »
Blossoming maps and their closure
[ blossoming map, bud, leaf] A blossoming map b is a map with additional stems attached to its corners. These stems are oriented and hence can be of two types; an outgoing stem is called a bud, while an ingoing stem is called a leaf. We require that a blossoming map has as many buds as leaves. Blossoming maps are always assumed to be rooted on a bud.
[ interior map] The interior map of a blossoming map b, denoted b, is the map obtained from b by removing all its stems. Most blossoming maps we usually consider are oriented, which leads to these additional definitions: [ blossoming degrees] In a blossoming oriented map, the interior degree (resp. blossoming degree, resp. degree) of a vertex is the degree of this vertex in the interior map (resp. the number of stems attached to it, resp. the sum of the interior and blossoming degrees). These can all be refined into ingoing and outgoing degrees. As stated in Théorème 1.1.2, unicellular blossoming maps are instrumental to our approach, because they can encode maps, while being easier to analyse. To describe the bijection mentioned in Théorème 1.1.2, called the closing algorithm, we first introduce the contour word of a blossoming unicellular map. [ contour word] Let b be a blossoming unicellular map. The contour word of b is the word on 2 letters U and D defined as follows: when doing a clockwise tour of the unique face (which means that the face is on the right), starting from the root bud, write U (for up-step) for each bud and D (for down-step) for each leaf. The contour word can naturally be seen as a 1-dimensional walk with up- and down-steps, starting and ending at height 0. We describe in Algorithm 8 how a unicellular blossoming map can be closed into a general map (see Figure 1.4 for a planar example, and Figure 1.7 from right to
left for a genus-1 example). The result of the closing algorithm applied to a map b is called the closure of b and denoted Close(b). Note that the way stems are matched, which is similar to a well-parenthesizing matching, implies that the created edges are non-crossing. Note also that the cyclic definition of the closing algorithm means that the matching does not depend on the root. This implies that several blossoming unicellular maps can lead to the same map, up to the position of the root. However this is not the case anymore if we restrict the way a blossoming map can be rooted.
[well-rooted] A map b is called well-rooted if its contour word is a Dyck word. Remark 11. When applying the closing algorithm to a well-rooted map, since the contour word is a Dyck path, the cyclic definition of the algorithm is not needed, Let b be a unicellular blossoming map. We write the contour word of b and match its steps by pairs upstep/downstep: each up-step U going from height i to i + 1 is matched to the first down-step D after U going from height i + 1 to i.
This is done in a cyclic manner, meaning that if there is no downstep going from height i+1 to height i after the last upstep of the contour word going from height i to height i+1, then this last upstep is to be matched with the first downstep going from height i+1 to height i, whose existence is assured by the fact that the contour word ends at height 0. The stems corresponding to matched steps are then merged into a single oriented edge. The new map is rooted on the corner just on the right of the edge formed by the former root bud, around the root vertex.
Opening a bicolorable map
We are now willing to apply the opening algorithm to bicolorable maps with dualgeodesic orientation, and prove that this yields a bijection. We first describe some properties that will prove useful to describe the resulting maps. [well-oriented map] A unicellular map b is well-oriented if in a tour of the face starting from the root, each edge is first followed backward and then forward. If b is a tree, this means that any interior edge is oriented toward the root. Note that this definition does not depend on whether the tour is clockwise or counterclockwise. Any unicellular map has a unique well-orientation, which can be straightforwardly obtained by doing a tour of the face. In relation to Remark 13, and in view of Section 1.4.1, this implies that the interior orientation of a well-rooted welloriented unicellular blossoming map b can be easily recovered from the unrooted map b if we know which rootable stem of b is the root of b. [well-labeled map] A blossoming oriented map is said to be well-labeled if its corners are labeled in such a way that:
• the labels of two corners adjacent around a vertex differ by 1, in which case the higher label is to the right of the separating edge (or stem),
• the labels of two corners adjacent along an edge coincide, and
• the root bud has labels 0 and 1.
Looking at the sequence of labels of corners around any fixed vertex, it is clear that the orientation of a well-labeled map is in particular Eulerian. Note that if the map has no stem, then having a well-labeling is equivalent to having a bicolorable orientation (indeed, the orientation of a dual edge corresponds to the difference of label between its endpoints, so that any dual cycle has as many forward and backward edges). In particular, this is stronger than having an Eulerian orientation. The set of well-rooted well-labeled well-oriented unicellular blossoming maps, counted by vertex degrees (similarly to bicolorable maps), is denoted O. The subset of O made of 4-valent maps is denoted O×. Recall from Equation (1.1) that the weight of a bicolorable map m is Q k>0 zv2k(m) k . Therefore, two maps have the same weight if and only if they have the same repartition of vertex degrees.
Reducing a unicellular map to a labeled scheme
The framework applied in this subsection has become classical when studying unicellular maps. In particular, it is developed by Chapuy, Marcus and Schaeffer in [CMS09]. [ extended scheme] The extended scheme of a unicellular blossoming map u is the unicellular map of genus g obtained by iteratively removing from the interior map u all vertices of interior degree 1.
A unicellular map u is composed of an extended scheme upon which are attached some stems and treelike parts. These treelike parts, with their leaves, are binary trees, oriented towards the root of the map. Furthermore, on each interior vertex of these trees is attached a bud. The set of such trees, counted by leaves, is denoted T . Its generating series satisfies the recurrence relation T(z) = z + 3T(z)2. The generating series of such trees with a marked leaf (or equivalently doubly rooted) is z · @T @z (z). The pruning procedure is defined as follows: each treelike part is replaced by a rootable stem: a root bud if the tree contains the root, a leaf otherwise (see Figure 1.11 left and middle). The image of U by the pruning procedure, counted by leaves, is denoted P.
Table of contents :
I Introduction et résumé
1 Cartes: énumeration, bijections
1.1 Échauffement: les cartes planaires 4-valentes
1.2 Énumération, rationalité, structure
1.2.1 Méthode de Tutte
1.2.2 Rationalité des séries génératrices de cartes non planaires
1.2.3 Rationalité bivariée
1.2.4 Autres résultats énumératifs concernant les cartes
1.2.5 Structure des orientations d’une carte
1.3 Combinatoire bijective des cartes
1.3.1 Bijections pour cartes planaires
1.3.2 Bijections pour cartes sur d’autres surfaces
1.3.3 Applications probabilistes
1.4 Les cartes: formalisme, propriétés
1.4.1 Surface, carte
1.4.2 Propriétés de cartes
1.4.3 Marches
2 Bijection bourgeonnante sur une surface quelconque
2.1 L’ouverture
2.1.1 Ouverture d’une carte de genre supérieur
2.1.2 Extension aux cartes non-bicoloriables
2.1.3 Extension aux cartes non orientables
2.1.4 Extension aux cartes pointées
2.2 Décomposition des cartes unicellulaires
2.2.1 Carte unicellulaire, coeur, schéma
2.2.2 Réenracinement
2.2.3 Élagage, raccourci, feuilles colorées
2.2.4 Le cas non-orientable: carte virtuellement enracinée, réenracinement sur un coin
2.3 Le cas 4-valent
2.3.1 Encodage des branches par des chemins de Motzkin
2.3.2 Le graphe d’inclinaison
2.4 Résultats énumératifs
2.4.1 Rationalité univariée en groupant par une surjection
2.4.2 Rationalité en groupant par une permutation
2.4.3 Rationalité pour les schémas avec cycles inclinés
2.5 Extension au cas des hexangulations biparties
2.6 bijections bourgeonnantes, multitriangulations, quid des autres surfaces?
3 Multitriangulations sur une surface quelconque
3.1 Introduction
3.2 Multitriangulations d’un polygone infini
3.2.1 Polygones infinis
3.2.2 Multitriangulations infinies
3.3 Multitriangulations d’une surface quelconque
3.3.1 Surfaces et revêtement universel
3.3.2 k-croisement, k-étoile et k-triangulations sur une surface quelconque
3.3.3 Propriétés structurelles
3.4 Multitriangulations d’un demi-cylindre
3.4.1 Demi-cylindre avec deux points marqués
3.4.2 Demi-cylindre quelconque
3.5 Ouvertures probabilistes
3.5.1 Grande multitriangulation aléatoire du disque
3.5.2 Multitriangulation infinies et limites de multitriangulations
3.5.3 k-triangulation du disque, (2k + 1)-angulations de grand genre
II Blossoming bijection for pointed maps on any surface
1 Blossoming bijection for higher-genus maps
1.1 Introduction
1.2 Orientations in higher genus
1.2.1 General
1.2.2 Structure of orientations of a graph
1.3 Closing and opening maps
1.3.1 Blossoming maps and their closure
1.3.2 The opening algorithm
1.3.3 Opening a bicolorable map
1.4 Enumeration and rationality
1.4.1 Getting rid of well-rootedness
1.4.2 Reducing a unicellular map to a labeled scheme
1.4.3 Analyzing a scheme
1.4.4 The offset graph
1.5 Rationality of maps with a given scheme
1.5.1 Counting rerooted pruned maps
1.5.2 Proof of the symmetry
1.5.3 Proof of the sum cancellation
1.6 Opening non-bicolorable maps
2 Bivariate rationality of higher-genus maps
2.1 Introduction
2.2 Notations, definitions and first constructions
2.2.1 Notations
2.2.2 Maps
2.2.3 Orientations
2.2.4 Blossoming maps, blossoming cores, blossoming schemes .
2.3 Bijection for higher-genus maps, counting vertices and faces
2.3.1 Closure of blossoming maps
2.3.2 Good blossoming maps and closures
2.3.3 From unicellular maps to schemes
2.3.4 Proof of Theorem 2.3.11
2.4 Criterion for rationality via Motzkin walks
2.4.1 Weighted Motzkin paths
2.4.2 Symmetry and rationality
2.4.3 Decomposition of cores
2.5 Bijective proof of the rationality of Mg(z•, z)
2.5.1 Definitions and offset graph
2.5.2 The univariate case
2.5.3 The bivariate case
3 Blossoming bijection and parametric rationality on any surface
3.1 Introduction
3.1.1 Enumeration – solving functional equations
3.1.2 Enumeration – understanding the nature of enumerated objects
3.1.3 Organization of the paper
3.2 Definitions
3.3 Bijection
3.3.1 Left-most geodesic tree
3.3.2 Blossoming unicellular maps
3.3.3 Opening of a map along a spanning tree
3.3.4 Closing a unicellular blossoming map
3.3.5 Opening and closure are inverse bijections
3.3.6 An opening bijection for general maps
3.4 Decomposition of a unicellular map
3.4.1 Core, scheme
3.4.2 Rerooting
3.4.3 The shortcut algorithm
3.5 The 4-valent case
3.5.1 Motzkin paths
3.5.2 Branches as Motzkin paths
3.5.3 Structure of the offset submap
3.6 Enumerative results for general maps
3.6.1 Rationality in D
3.6.2 Rationality for schemes with no offset cycle
3.6.3 Rationality for schemes with offset loops
III Multitriangulations on any surface
1 Multitriangulations on any surface
1.1 Multitriangulations of infinite polygons
1.1.1 Infinite polygons
1.1.2 Infinite multitriangulations
1.1.3 Proof of Theorem 1.1.8
1.2 Multitriangulations of a general surface
1.2.1 Surfaces and their universal covers
bijections bourgeonnantes, multitriangulations, quid des autres surfaces?
1.2.2 k-crossings, k-stars and k-triangulations on surfaces
1.2.3 Structural properties
1.3 Multitriangulations of the half-cylinder
1.3.1 Half-cylinder with two marked points
1.3.2 Half-cylinders with arbitrary many marked points .
