A Bijection for Rooted Maps on Orientable Surfaces

DOI10.1137/080720097MaRDI QIDQ3583328zbMATH OpenOpenAlexFDO

Authors Guillaume Chapuy, Michel Marcus, Gilles Schaeffer

Publication date 27 August 2010

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

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

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)

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.

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

Cited in

(68)

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