Guillaume Chapuy - Are even maps on surfaces likely to be bipartite?

dmtcs:3577 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science - https://doi.org/10.46298/dmtcs.3577
Are even maps on surfaces likely to be bipartite?Article

Authors: Guillaume Chapuy 1

  • 1 Laboratoire d'informatique de l'École polytechnique [Palaiseau]

It is well known that a planar map is bipartite if and only if all its faces have even degree (what we call an even map). In this paper, we show that rooted even maps of positive genus $g$ chosen uniformly at random are bipartite with probability tending to $4^{−g}$ when their size goes to infinity. Loosely speaking, we show that each of the $2g$ fundamental cycles of the surface of genus $g$ contributes a factor $\frac{1}{2}$ to this probability.We actually do more than that: we obtain the explicit asymptotic behaviour of the number of even maps and bipartite maps of given genus with any finite set of allowed face degrees. This uses a generalisation of the Bouttier-Di Francesco-Guitter bijection to the case of positive genus, a decomposition inspired by previous works of Marcus, Schaeffer and the author, and some involved manipulations of generating series counting paths. A special case of our results implies former conjectures of Gao.


Volume: DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: lattice walk,algebraic series,labelled trees,graphs on surfaces,5C78 (05A15),[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : OpenAIRE Graph
  • Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.; Funder: European Commission; Code: 208471; Call ID: ERC-2007-StG; Projet Financing: EC:FP7:ERC

Consultation statistics

This page has been seen 162 times.
This article's PDF has been downloaded 145 times.