Academic literature on the topic 'Énumération asymptotique'

International audience This extended abstract presents some recent (exact and asymptotic) enumerative results concerning rhombustilings of hexagons that have had symmetrically distributed inward pointing triangles of side length 2 removedfrom their interiors. These results form part of a larger article that is currently available online (arXiv:1501.05772). Ce résumé détaillé présente quelques résultats énumératifs récents (exacts et asymptotiques) sur les pavagespar losanges d’hexagones dont on a enlevé des triangles de côté 2 placés symétriquement et pointant vers l’intérieur.Ces résultats sont extraits d’un article plus développé disponible actuellement en ligne (arXiv:1501.05772).

Constellations and hypermaps generalize combinatorial maps, $\textit{i.e.}$ embedding of graphs in a surface, in terms of factorization of permutations. In this paper, we extend a result of Jackson and Visentin (1990) on an enumerative relation between quadrangulations and bipartite quadrangulations. We show a similar relation between hypermaps and constellations by generalizing a result in the original paper on factorization of characters. Using this enumerative relation, we recover a result on the asymptotic behavior of hypermaps of Chapuy (2009). Les constellations et les hypercartes généralisent les cartes combinatoires, $\textit{i.e.}$ les plongements de graphe dans une surface, en terme de factorisation de permutations. Dans cet article, nous généralisons un résultat de Jackson et Visentin (1990) sur une relation énumérative entre les quadrangulations ordinaires et biparties. Nous montrons une relation similaire entre les constellations et les hypercartes en généralisant un résultat de factorisation de caractère. Avec cette relation, on retrouve un résultat sur le comportement asymptotique des hypercartes dans Chapuy (2009).

Cette thèse présente quelques contributions à l’étude des fonctions de comptage des graphes en rubans métriques. Un graphe en ruban, aussi connu sous le nom de carte combinatoire, est un plongement cellulaire d’un graphe dans une surface. On peut le représenter via le recollements de polygones ou encore via des factorisations de permutations. Une métrique sur un graphe en rubans est l’attribution d’une longueur strictement positive à chaque arête. Les fonctions de comptage donnent le nombre de graphes en rubans avec une métrique entière et combinatoire fixée (genre de la surface, degré des sommets, nombre de bords) en fonction des périmètres des bords. Notre approche à l’étude de ces fonctions est purement combinatoire et repose sur l’utilisation des bijections et chirurgies pour les graphes en rubans. Dans un premier temps, on montre que ces fonctions sont (quasi-)polynomiales par morceaux, et on précise les régions de (quasi-)polynomialité. Ensuite, on étudie les cas où leur termes de plus haut degré sont de vrais polynômes. Notre intérêt dans ces cas vient du fait que les polynômes correspondants sont utiles pour l’énumération des surfaces à petits carreaux, qui correspondent aux points entiers des strates des surfaces de (demi-)translation (de manière équivalent, states des différentielles sur les surfaces de Riemann). Par conséquent, on peut donner des formules raffinées/alternatives pour les volumes de Masur-Veech des strates. Un exemple connu sont les polynômes de Kontsevich, qui comptent les graphes en rubans métriques trivalents de genre et périmètres des bords fixés. Ils ont été utilisés récemment par Delecroix, Goujard, Zograf et Zorich pour obtenir une formule combinatoire pour les volumes des strates principales des différentielles quadratiques. On se concentre sur les graphes en rubans métriques face-bipartis, qui apparaissent dans l’étude des différentielles Abéliennes. On montre que pour les graphes à un sommet, les termes de plus haut degré des fonctions de comptage sur certains sous-espaces sont des polynômes explicites. En conséquence, on obtient la série génératrice des contributions des surfaces à petits carreaux à n cylindres aux volumes des strates minimales des différentielles Abéliennes, raffinant un résultat précédent de Sauvaget. Ensuite, on présente un résultat de polynomialité similaire pour les deux sous-familles de graphes qui correspondent ou composants connexes de strates minimales de parité spin paire/impaire. Cela donne un raffinement d’une formule pour les différences des volumes correspondants obtenue précédemment par Chen, Möller, Sauvaget et Zagier. Puis on conjecture que le phénomène de polynomialité reste vrai pour les familles de graphes à plusieurs sommets, si chaque graphe est pondéré par le comptage de certains arbres couvrants. On prouve cette conjecture dans le cas planaire. En chemin, on construit des familles d’arbres plans qui correspondent à certaines triangulations de produits de simplexes qui représentent un intérêt du point de vue de la théorie des polytopes. Finalement, on présente une contribution au projet commun avec Duryev et Goujard, où la formule combinatoire de Delecroix, Goujard, Zograf et Zorich est généralisée aux strates des différentielles quadratiques aux singularités impaires. La contribution est une preuve combinatoire de la formule pour les coefficients qui comptent certaines dégénérescences des graphes en ruban métriques non-face-biparti
This thesis presents several contributions to the study of counting functions for metric ribbon graphs. Ribbon graphs, also known as combinatorial maps, are cellular embeddings of graphs in surfaces modulo homeomorphisms. They are combinatorial objects that can be represented as gluings of polygons or factorizations of permutations. Metric on a ribbon graph is an assignment of positive lengths to its edges. The counting functions give the number of integral metric ribbon graphs with fixed combinatorics (genus of the surface, degrees of vertices, number of boundaries) as a function of the perimeters of the boundaries. Our approach to their study is purely combinatorial and relies on bijections and surgeries for ribbon graphs. Firstly, we show that these functions are piecewise (quasi-)polynomials, specifying exactly the regions of (quasi-)polynomiality. We then study the cases when their top-degree terms are honest polynomials. Our interest in such cases comes from the fact that the corresponding polynomials can be used for refined enumeration of square-tiled surfaces, which correspond to integer points in the strata of (half-)translations surfaces (equivalently, strata of differentials on Riemann surfaces). Consequently, one can give refined/alternative formulas for Masur-Veech volumes of strata. One known example are the Kontsevich polynomials, counting trivalent metric ribbon graphs of given genus and perimeters of boundaries. They were recently used by Delecroix, Goujard, Zograf and Zorich to give a combinatorial formula for the volumes of principal strata of quadratic differentials. We concentrate on face-bipartite metric ribbon graphs, which appear in the study of Abelian differentials. We show that in the case of one-vertex graphs the top-degree terms of the counting functions on certain subspaces are in fact (explicit) polynomials. As a consequence, we deduce the generating function for the contributions of n-cylinder square-tiled surfaces to the volumes of minimal strata of Abelian differentials, refining a previous result of Sauvaget. We then present a similar polynomiality result for the two subfamilies of graphs corresponding to even/odd spin connected components of the minimal strata. This also gives a refinement of a formula for the corresponding volume differences previously obtained by Chen, Möller, Sauvaget and Zagier. Next we conjecture that the polynomiality phenomenon holds for families of graphs with several vertices, if each graph is weighted by the count of certain spanning trees. We prove the conjecture in the planar case. In the process, we construct families of plane trees which correspond to certain triangulations of the product of two simlpices, which are interesting from the point of view of the theory of polytopes. Finally, we present a contribution to a joint work with Duryev and Goujard, where the combinatorial formula of Delecroix, Goujard, Zograf and Zorich is generalized to all strata of quadratic differentials with odd singularities. The contribution is a combinatorial proof of the formula for coefficients counting certain degenerations of (non-face-bipartite) metric ribbon graphs

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).

La géométrie complexe est un outil puissant pour étudier les systèmes intégrables classiques, la physique statistique sur réseau aléatoire, les problèmes de matrices aléatoires, la théorie topologique des cordes, ...Tous ces problèmes ont en commun la présence de relations, appelées équations de boucle ou contraintes de Virasoro. Dans le cas le plus simple, leur solution complète a été trouvée récemment, et se formule naturellement en termes de géométrie différentielle sur une surface de Riemann : la "courbe spectrale", qui dépend du problème. Cette thèse est une contribution au développement de ces techniques et de leurs applications.Pour commencer, nous abordons les questions de développement asymptotique à tous les ordres lorsque N tend vers l'infini, des intégrales N-dimensionnelles venant de la théorie des matrices aléatoires de taille N par N, ou plus généralement des gaz de Coulomb. Nous expliquons comment établir, dans les modèles de matrice beta et dans un régime à une coupure, le développement asymptotique à tous les ordres en puissances de N. Nous appliquons ces résultats à l'étude des grandes déviations du maximum des valeurs propres dans les modèles beta, et en déduisons de façon heuristique des informations sur l'asymptotique à tous les ordres de la loi de Tracy-Widom beta, pour tout beta positif. Ensuite, nous examinons le lien entre intégrabilité et équations de boucle. En corolaire, nous pouvons démontrer l'heuristique précédente concernant l'asymptotique de la loi de Tracy-Widom pour les matrices hermitiennes.Nous terminons avec la résolution de problèmes combinatoires en toute topologie. En théorie topologique des cordes, une conjecture de Bouchard, Klemm, Mariño et Pasquetti affirme que des séries génératrices bien choisies d'invariants de Gromov-Witten dans les espaces de Calabi-Yau toriques, sont solution d'équations de boucle. Nous l'avons démontré dans le cas le plus simple, où ces invariants coïncident avec les nombres de Hurwitz simples. Nous expliquons les progrès récents vers la conjecture générale, en relation avec nos travaux. En physique statistique sur réseau aléatoire, nous avons résolu le modèle O(n) trivalent sur réseau aléatoire introduit par Kostov, et expliquons la démarche à suivre pour résoudre des modèles plus généraux.Tous ces travaux soulignent l'importance de certaines "intégrales de matrices généralisées" pour les applications futures. Nous indiquons quelques éléments appelant à une théorie générale, encore basée sur des "équations de boucles", pour les calculer

La géométrie complexe est un outil puissant pour étudier les systèmes intégrables classiques, la physique statistique sur réseau aléatoire, les problèmes de matrices aléatoires, la théorie topologique des cordes, …Tous ces problèmes ont en commun la présence de relations, appelées équations de boucle ou contraintes de Virasoro. Dans le cas le plus simple, leur solution complète a été trouvée récemment, et se formule naturellement en termes de géométrie différentielle sur une surface de Riemann : la "courbe spectrale", qui dépend du problème. Cette thèse est une contribution au développement de ces techniques et de leurs applications.Pour commencer, nous abordons les questions de développement asymptotique à tous les ordres lorsque N tend vers l’infini, des intégrales N-dimensionnelles venant de la théorie des matrices aléatoires de taille N par N, ou plus généralement des gaz de Coulomb. Nous expliquons comment établir, dans les modèles de matrice beta et dans un régime à une coupure, le développement asymptotique à tous les ordres en puissances de N. Nous appliquons ces résultats à l'étude des grandes déviations du maximum des valeurs propres dans les modèles beta, et en déduisons de façon heuristique des informations sur l'asymptotique à tous les ordres de la loi de Tracy-Widom beta, pour tout beta positif. Ensuite, nous examinons le lien entre intégrabilité et équations de boucle. En corolaire, nous pouvons démontrer l'heuristique précédente concernant l'asymptotique de la loi de Tracy-Widom pour les matrices hermitiennes.Nous terminons avec la résolution de problèmes combinatoires en toute topologie. En théorie topologique des cordes, une conjecture de Bouchard, Klemm, Mariño et Pasquetti affirme que des séries génératrices bien choisies d'invariants de Gromov-Witten dans les espaces de Calabi-Yau toriques, sont solution d'équations de boucle. Nous l'avons démontré dans le cas le plus simple, où ces invariants coïncident avec les nombres de Hurwitz simples. Nous expliquons les progrès récents vers la conjecture générale, en relation avec nos travaux. En physique statistique sur réseau aléatoire, nous avons résolu le modèle O(n) trivalent sur réseau aléatoire introduit par Kostov, et expliquons la démarche à suivre pour résoudre des modèles plus généraux.Tous ces travaux soulignent l'importance de certaines "intégrales de matrices généralisées" pour les applications futures. Nous indiquons quelques éléments appelant à une théorie générale, encore basée sur des "équations de boucles", pour les calculer
Complex analysis is a powerful tool to study classical integrable systems, statistical physics on the random lattice, random matrix theory, topological string theory, … All these topics share certain relations, called "loop equations" or "Virasoro constraints". In the simplest case, the complete solution of those equations was found recently : it can be expressed in the framework of differential geometry over a certain Riemann surface which depends on the problem : the "spectral curve". This thesis is a contribution to the development of these techniques, and to their applications.First, we consider all order large N asymptotics in some N-dimensional integrals coming from random matrix theory, or more generally from "log gases" problems. We shall explain how to use loop equations to establish those asymptotics in beta matrix models within a one cut regime. This can be applied in the study of large fluctuations of the maximum eigenvalue in beta matrix models, and lead us to heuristic predictions about the asymptotics of Tracy-Widom beta law to all order, and for all positive beta. Second, we study the interplay between integrability and loop equations. As a corollary, we are able to prove the previous prediction about the asymptotics to all order of Tracy-Widom law for hermitian matrices.We move on with the solution of some combinatorial problems in all topologies. In topological string theory, a conjecture from Bouchard, Klemm, Mariño and Pasquetti states that certain generating series of Gromov-Witten invariants in toric Calabi-Yau threefolds, are solutions of loop equations. We have proved this conjecture in the simplest case, where those invariants coincide with the "simple Hurwitz numbers". We also explain recent progress towards the general conjecture, in relation with our work. In statistical physics on the random lattice, we have solved the trivalent O(n) model introduced by Kostov, and we explain the method to solve more general statistical models.Throughout the thesis, the computation of some "generalized matrices integrals" appears to be increasingly important for future applications, and this appeals for a general theory of loop equations

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