Enumeration and analysis of models of planar maps via the bijective method

Abstract : Bijective combinatorics is a field which consists in studying the enumerative properties of some families of mathematical objects, by exhibiting bijections (ideally explicit) which preserve these properties between such families and already known objects. One can then apply any tool of analytic combinatorics to these new objets, in order to get explicit enumeration, asymptotics properties, or to perform random sampling.In this thesis, we will be interested in planar maps – graphs drawn on the plane with no crossing edges. First, we will recover a simple formula –obtained by Eynard – for the generating series of bipartite maps and quasi-bipartite maps with boundaries of prescribed lengths, and we will give anatural generalization to p-constellations and quasi-p-constellations. In the second part of this thesis, we will present an original bijection for outertriangular simple maps – with no loops nor multiple edges – and eulerian triangulations. We then use this bijection to design random samplers for rooted simple maps according to the number of vertices and edges. We will also study the metric properties of simple maps by proving the convergence of the rescaled distance-profile towards an explicit random measure related to the Brownian snake.
Document type :
Theses
Complete list of metadatas

Cited literature [60 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/tel-01084964
Contributor : Gwendal Collet <>
Submitted on : Thursday, November 20, 2014 - 2:24:06 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:27 PM
Long-term archiving on : Monday, February 23, 2015 - 8:48:53 AM

Identifiers

  • HAL Id : tel-01084964, version 1

Collections

Citation

Collet Gwendal. Enumeration and analysis of models of planar maps via the bijective method. Combinatorics [math.CO]. École Polytechnique, 2014. English. ⟨tel-01084964⟩

Share

Metrics

Record views

279

Files downloads

267