Cette these traite de l'algorithmique des cartes planaires (graphes dessines dans le plan sans intersection d'aretes) et propose des procedures efficaces pour le codage, la generation aleatoire, et le dessin de plusieurs familles importantes: 3-connexes, triangulations, quadrangulations... En particulier, on decrit le premier algorithme optimal de codage des incidences faces-aretes-sommets des maillages polygonaux de topologie spherique, qui atteint la borne inferieure de 2bits par arete. En partant d'un generateur de cartes 3-connexes, on developpe un nouveau generateur aleatoire uniforme de graphes planaires dont la complexite est la meilleure connue actuellement: quadratique (en esperance) en taille exacte et lineaire (en esperance) en taille approchee. Enfin, on donne plusieurs algorithmes de dessin en lignes droites (aretes representees par des segments) de cartes planaires sur la grille. Les procedures de dessin sont a la fois tres simples a decrire et donnent les meilleures performance (en probabilite) pour le dessin de deux familles de cartes: les triangulations du carre sans 3-cycle rempli —dite irreductibles— et les quadrangulations. Pour developper les algorithmes presentes dans la these, on exploite plusieurs structures combinatoires sur les cartes (orientations specifiques, partitions en arbres couvrants...) ainsi que de nouvelles constructions bijectives.

Cette thèse propose une modélisation basée sur les cartes planaires. Les données d'un même niveau plan sont modélisées, selon leur sémantique, par des cartes planaires indépendantes qui sont superposées. L'empilement de telles cartes, géré par une représentation tridimensionnelle inspirée des techniques de dessin en perspective cavalière, permet de modéliser des données appartenant à des plans strictement parallèles. Une structure de données hiérarchique offre la possibilité de détailler une zone d'un plan (face d'une carte planaire) par un certain nombre de cartes planaires représentant différentes sémantiques. De plus, cette modélisation gère parfaitement les liens qui peuvent exister entre les objets modélises dans différentes cartes planaires. Elle permet ainsi de garder le sens global de l'ensemble des objets. Cette modélisation a été utilisée pour réaliser une interface graphique dans le cadre d'un projet européen esprit. Une évaluation ergonomique de cette interface est présentée ainsi que les améliorations apportées à cette interface suite à l'évaluation.

Dans ce travail, nous nous sommes intéressés à l'étude asymptotique d'objets combinatoires aléatoires. Deux thèmes ont particulièrement retenu notre attention : les cartes planaires aléatoires et les modèles combinatoires liés à la théorie des fragmentations. La théorie mathématique des cartes planaires aléatoires est née à l'aube de notre millénaire avec les travaux pionniers de Benjamini & Schramm, Angel & Schramm et Chassaing & Schaeffer. Elle a ensuite beaucoup progressé, mais à l'heure où ces lignes sont écrites, de nombreux problèmes fondamentaux restent ouverts. Résumons en quelques mots clés nos principales contributions dans le domaine : l'introduction et l'étude du cactus brownien (avec J.F. Le Gall et G. Miermont), l'étude de la quadrangulation infinie uniforme vue de l'infini (avec L. Ménard et G. Miermont), ainsi que des travaux plus théoriques sur les graphes aléatoires stationnaires d'une part et les graphes empilables dans $\R^d$ d'autre part (avec I. Benjamini). La théorie des fragmentations est beaucoup plus ancienne et remonte à des travaux de Kolmogorov (1941) et de Filippov (1961). Elle est maintenant bien développée (voir par exemple l'excellent livre de J. Bertoin), et nous ne nous sommes pas focalisés sur cette théorie mais plutôt sur ses applications à des modèles combinatoires. Elle s'avère en effet très utile pour étudier différents modèles de triangulations récursives du disque (travail effectué avec J.F. Le Gall) et les recherches partielles dans les quadtrees (travail effectué avec A. Joseph).

Ce manuscrit est un document de synthèse et de présentation d'une majorité des travaux que j'ai effectués entre septembre 2008 et septembre 2013 (voir la liste des publications ci-dessous1). Les publications [P1-6] sont issues de la thèse ainsi qu'une grande partie de [P11]. Afin de présenter un document concis et cohérent nous avons choisi de ne pas traiter les publications [P3], [P5], [P9] et [P10]. Que mes co-auteurs m'excusent. Le document est construit autour de deux parties principales : les arbres aléatoires d'une part et les cartes planaires aléatoires d'autre part. Les contributions originales sont signalées par des théorèmes encadrés et sont numérotés 1, 2, 3, . . ..

Dans ce travail, nous nous sommes intéressés à l'étude asymptotique d'objets combinatoires aléatoires. Deux thèmes ont particulièrement retenu notre attention : les cartes planaires aléatoires et les modèles combinatoires liés à la théorie des fragmentations. La théorie mathématique des cartes planaires aléatoires est née à l'aube de notre millénaire avec les travaux pionniers de Benjamini & Schramm, Angel & Schramm et Chassaing & Schaeffer. Elle a ensuite beaucoup progressé, mais à l'heure où ces lignes sont écrites, de nombreux problèmes fondamentaux restent ouverts. Résumons en quelques mots clés nos principales contributions dans le domaine : l'introduction et l'étude du cactus brownien (avec J.F. Le Gall et G. Miermont), l'étude de la quadrangulation infinie uniforme vue de l'infini (avec L. Ménard et G. Miermont), ainsi que des travaux plus théoriques sur les graphes aléatoires stationnaires d'une part et les graphes empilables dans $\R^d$ d'autre part (avec I. Benjamini). La théorie des fragmentations est beaucoup plus ancienne et remonte à des travaux de Kolmogorov (1941) et de Filippov (1961). Elle est maintenant bien développée (voir par exemple l'excellent livre de J. Bertoin), et nous ne nous sommes pas focalisés sur cette théorie mais plutôt sur ses applications à des modèles combinatoires. Elle s'avère en effet très utile pour étudier différents modèles de triangulations récursives du disque (travail effectué avec J.F. Le Gall) et les recherches partielles dans les quadtrees (travail effectué avec A. Joseph). / The subject of this thesis is the asymptotic study of large random combinatorial objects. This is obviously very broad, and we focused particularly on two themes: random planar maps and their limits, and combinatorial models that are in a way linked to fragmentation theory. The mathematical theory of random planar maps is quite young and was triggered by works of Benjamini & Schramm, Angel & Schramm and Chassaing & Schaeffer. This fascinating field is still growing and fundamental problems remain unsolved. We present some new results in both the scaling limit and local limit theories by introducing and studying the Brownian Cactus (with J.F. Le Gall and G. Miermont), giving a new view point, a view from infinity, at the Uniform Infinite Planar Quadrangulation (UIPQ) and bringing more theoretical contributions on stationary random graphs and sphere packable graphs (with I. Benjamini). Fragmentation theory is much older and can be tracked back to Kolmogorov and Filippov. Our goal was not to give a new abstract contribution to this well-developed theory (see the beautiful book of J. Bertoin) but rather to apply it to random combinatorial objects. Indeed, fragmentation theory turned out to be useful in the study of the so-called random recursive triangulations of the disk (joint work with J.F. Le Gall) and partial match queries in random quadtrees (joint work with A. Joseph).

Cette thèse porte sur le polynôme de Tutte, étudié selon différents points de vue. Dans une première partie, nous nous intéressons à l’énumération des cartes planaires munies d’une forêt couvrante, ici appelées cartes forestières, avec un poids z par face et un poids u par composante non racine de la forêt. De manière équivalente, nous comptons selon le nombre de faces les cartes planaires C pondérées par TC(u + 1; 1), où TC désigne le polynôme de Tutte de C. Nous commençons par une caractérisation purement combinatoire de la série génératrice correspondante, notée F(z; u). Nous en déduisons que F(z; u) est différentiellement algébrique en z, c’est-à-dire que F satisfait une équation différentielle polynomiale selon z. Enfin, pour u ≥ -1, nous étudions le comportement asymptotique du n-ième coefficient de F(z; u). Nous observons une transition de phase en 0, avec notamment un régime très atypique en n-3 ln-2(n) pour u ϵ [-1; 0[, témoignant d’une nouvelle classe d’universalité pour les cartes planaires. Dans une seconde partie, nous proposons un cadre unificateur pour les différentes notions d’activités utilisées dans la littérature pour décrire le polynôme de Tutte.La nouvelle notion d’activité ainsi définie est appelée Δ-activité. Elle regroupe toutes les notions d’activité déjà connues et présente de belles propriétés, comme celle de Crapo qui définit une partition (adaptée à l’activité) du treillis des sous-graphes couvrants en intervalles. Nous conjecturons en dernier lieu que toute activité qui décrit le polynôme de Tutte et qui satisfait la propriété susmentionnée de Crapo peut être définie en termes de Δ-activités. / This thesis deals with the Tutte polynomial, studied from different points of view. In the first part, we address the enumeration of planar maps equipped with a spanning forest, here called forested maps, with a weight z per face and a weight u per non-root component of the forest. Equivalently, we count (with respect to the number of faces) the planar maps C weighted by TC(u + 1; 1), where TC is the Tutte polynomial of C.We begin by a purely combinatorial characterization of the corresponding generating function, denoted by F(z; u). We deduce from this that F(z; u) is differentially algebraic in z, that is, satisfies a polynomial differential equation in z. Finally, for u ≥ -1, we study the asymptotic behaviour of the nth coefficient of F(z; u).We observe a phase transition at 0, with a very unusual regime in n-3 ln-2(n) for u ϵ [-1; 0[, which testifiesa new universality class for planar maps. In the second part, we propose a framework unifying the notions of activity used in the literature to describe the Tutte polynomial. The new notion of activity thereby defined is called Δ-activity. It gathers all the notions of activities that were already known and has nice properties, as Crapo’s property that defines a partition of the lattice of the spanning subgraphs into intervals with respect to the activity. Lastly we conjecture that every activity that describes the Tutte polynomial and that satisfies Crapo’s property can be defined in terms of Δ-activity.

Les cartes planaires sont des graphes planaires dessinés sur la sphère et vus à déformation près. De nombreuses propriétés des cartes sont supposées universelles, dans le sens où elles ne dépendent pas des détails du modèle choisi. Nous commençons par établir une inégalité isopérimétrique dans la quadrangulation infinie du plan. Nous confirmons également une conjecture de Krikun portant sur la longueur des cycles les plus courts séparant la boule de rayon $r$ de l'infini. Dans un deuxième temps, nous nous intéressons à l'effet de modifications de distances sur la géométrie à grande échelle des quadrangulations uniformes, élargissant la classe d'universalité de la carte brownienne. Nous montrons également que la bijection de Tutte, entre quadrangulations et cartes planaires, est asymptotiquement une isométrie. Enfin, nous établissons une borne supérieure sur le temps de mélange de la marche aléatoire dans les cartes aléatoires. / Planar maps are planar graphs drawn on the sphere and seen up to deformation. Many properties of maps are conjectured to be universal, in the sense that they do not depend on the details of the model.We begin by establishing an isoperimetric inequality in the infinite quadrangulation of the plane. We also confirm a conjecture by Krikun concerning the length of the shortest cycles separating the ball of radius $r$ from infinity. We then consider the effect of modifications of distances on the large-scale geometry of uniform quadrangulations, extending the universality class of the Brownian map. We also show that the Tutte bijection, between quadrangulations and planar maps, is asymptotically an isometry. Finally, we establish an upper bound on the mixing time of the random walk in random maps.

Nous nous intéressons à trois problèmes issus du monde des arbres aléatoires discrets et continus. Dans un premier lieu, nous faisons une étude générale des arbres de fragmentation auto-similaires, étendant certains résultats de Haas et Miermont en 2006, notamment en calculant leur dimension de Hausdorff sous des hypothèses malthusiennes. Nous nous intéressons ensuite à une suite particulière d’arbres discrets k-aires, construite de manière récursive avec un algorithme similaire à celui de Rémy de 1985. La taille de l’arbre obtenu à la n-ième étape est de l’ordre de n^(1/k), et après renormalisation, on trouve que la suite converge en probabilité vers un arbre de fragmentation. Nous étudions également des manières de plonger ces arbres les uns dans les autres quand k varie. Dans une dernière partie, nous démontrons la convergence locale en loi d’arbres de Galton-Watson multi-types critiques quand on les conditionne à avoir un grand nombre de sommets d’un certain type fixé. Nous appliquons ensuite ce résultat aux cartes planaires aléatoire pour obtenir la convergence locale en loi de grandes cartes de loi de Boltzmann critique vers une carte planaire infinie. / We study three problems related to discrete and continuous random trees. First, we do a general study of self-similar fragmentation trees, extending some results established by Haas and Miermont in 2006, in particular by computing the Hausdorff dimension of these trees under some Malthusian hypotheses. We then work on a particular sequence of k-ary growing trees, defined recursively with a similar method to Rémy’s algorithm from 1985. We show that the size of the tree obtained at the n-th step if of order n^(1/k), and, after renormalization, we prove that the sequence convergences to a fragmentation tree. We also study embeddings of the limiting trees as k varies. In the last chapter, we show the local convergence in distribution of critical multi-type Galton-Watson trees conditioned to have a large number of vertices of a fixed type. We then apply this result to the world of random planar maps, obtaining that large critical Boltzmann-distributed maps converge locally in distribution to an infinite planar map.