A Bijection for Rooted Maps on Orientable Surfaces

DOI10.1137/080720097zbMATH Open1207.05087arXiv0712.3649OpenAlexW1980941830MaRDI QIDQ3583328FDOQ3583328

Authors: Guillaume Chapuy, Michel Marcus, Gilles Schaeffer 

Publication date: 27 August 2010

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: The enumeration of maps and the study of uniform random maps have been classical topics of combinatorics and statistical physics ever since the seminal work of Tutte in the sixties. Following the bijective approach initiated by Cori and Vauquelin in the eighties, we describe a bijection between rooted maps, or rooted bipartite quadrangulations, on a surface of genus g and some simpler objects that generalize plane trees. Thanks to a rerooting argument, our bijection allows to compute the generating series of rooted maps on a surface of genus g with respect to the number of edges, and to recover the asymptotic numbers of such maps. Our construction allows to keep track in a bipartite quadrangulation of the distances of all vertices to a random basepoint. This is an analog for higher genus surfaces of the basic result on which were built the recent advances in the comprehension of the intrinsec geometry of large random planar maps, hopefully opening the way to the study of a model of continuum random surfaces of genus g.

Full work available at URL: https://arxiv.org/abs/0712.3649

Recommendations

• A bijection for rooted maps on general surfaces
• A bijection for rooted maps on general surfaces (extended abstract)
• A bijection for covered maps on orientable surfaces
• The number of rooted maps on an orientable surface
• A bijection for nonorientable general maps
• A bijection for nonorientable general maps
• The asymptotic number of rooted maps on a surface
• Counting rooted maps on a surface
• The number of rooted essential maps on surfaces
• A pattern for the asymptotic number of rooted maps on surfaces

zbMATH Keywords

treesgraphs on surfacesrandom discrete surfaces

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30)

Cited In (68)

• Large expanders in high genus unicellular maps
• Unicellular maps vs. hyperbolic surfaces in large genus: simple closed curves
• Are even maps on surfaces likely to be bipartite?
• Multiple scale asymptotics of map enumeration
• Bijective proof of the rationality of the generating series of higher-genus maps
• A bijection for rooted maps on general surfaces (extended abstract)
• Hypergraph matrix models and generating functions
• Relating random matrix map enumeration to a universal symbol calculus for recurrence operators in terms of Bessel-Appell polynomials
• Map enumeration from a dynamical perspective
• The mesoscopic geometry of sparse random maps
• Non-recursive counts of graphs on surfaces
• Random generation and scaling limits of fixed genus factorizations into transpositions
• The Brownian map is the scaling limit of uniform random plane quadrangulations
• Analytic combinatorics of chord and hyperchord diagrams with \(k\) crossings
• Blossoming bijection for higher-genus maps
• Spanning forests in regular planar maps
• Schnyder woods for higher genus triangulated surfaces, with applications to encoding
• Counting 2-connected 4-regular maps on the projective plane
• Reflection length with two parameters in the asymptotic representation theory of type B/C and applications
• Enumerating simplicial decompositions of surfaces with boundaries
• Planar maps and continued fractions
• Unified bijections for maps with prescribed degrees and girth
• Blossoming bijection for bipartite pointed maps and parametric rationality of general maps of any surface
• On the diameter of random planar graphs
• Liouville quantum gravity and KPZ
• Feynman diagrams, ribbon graphs, and topological recursion of Eynard-Orantin
• Compact Brownian surfaces
• The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees
• Topological phases: an expedition off lattice
• Planarity and non-separating cycles in uniform high genus quadrangulations
• Double scaling limit for the O(N)³-invariant tensor model
• Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth
• Geodesics in Brownian surfaces (Brownian maps)
• 4-edge-connected 4-regular maps on the projective plane
• Enumeration of non-oriented maps via integrability
• Simple formulas for constellations and bipartite maps with prescribed degrees
• The topology of scaling limits of positive genus random quadrangulations
• Generating functions of bipartite maps on orientable surfaces
• Invitation to random tensors
• Uniform infinite planar quadrangulations with a boundary
• An involution on bicubic maps and \beta(0,1)-trees
• Enumeration of chord diagrams without loops and parallel chords
• Limit laws of planar maps with prescribed vertex degrees
• Maps of unfixed genus and blossoming trees
• Short cycles in high genus unicellular maps
• The two-point function of bicolored planar maps
• A bijection for nonorientable general maps
• A bijection for nonorientable general maps
• A bijection for essentially 3-connected toroidal maps
• Large unicellular maps in high genus
• A bijection for covered maps, or a shortcut between Harer-Zagiers and Jacksons formulas
• Iterated foldings of discrete spaces and their limits: candidates for the role of Brownian map in higher dimensions
• Double scaling limit of multi-matrix models at large D
• The three-point function of general planar maps
• Enumeration of \(N\)-rooted maps using quantum field theory
• On tessellations of random maps and the \(t_g\)-recurrence
• On tessellations of random maps and the \(t_g\)-recurrence
• A new combinatorial identity for unicellular maps, via a direct bijective approach
• A generic method for bijections between blossoming trees and planar maps
• A bijection for essentially 4-connected toroidal triangulations
• Scaling limit of random planar quadrangulations with a boundary
• A bijection for covered maps on orientable surfaces
• Analyticity results for the cumulants in a random matrix model
• A bijection for rooted maps on general surfaces
• Simple recurrence formulas to count maps on orientable surfaces
• Counting unicellular maps on non-orientable surfaces
• Combinatorial theory of the semiclassical evaluation of transport moments II: Algorithmic approach for moment generating functions
• Encoding toroidal triangulations

This page was built for publication: A Bijection for Rooted Maps on Orientable Surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3583328)