Unified bijections for maps with prescribed degrees and girth

DOI10.1016/J.JCTA.2012.03.007zbMATH Open1242.05124arXiv1102.3619OpenAlexW2073442617MaRDI QIDQ423656FDOQ423656

Éric Fusy, Olivier Bernardi

Publication date: 4 June 2012

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: This article presents unified bijective constructions for planar maps, with control on the face degrees and on the girth. Recall that the girth is the length of the smallest cycle, so that maps of girth at least $d=1,2,3$ are respectively the general, loopless, and simple maps. For each positive integer $d$, we obtain a bijection for the class of plane maps (maps with one distinguished root-face) of girth $d$ having a root-face of degree $d$. We then obtain more general bijective constructions for annular maps (maps with two distinguished root-faces) of girth at least $d$. Our bijections associate to each map a decorated plane tree, and non-root faces of degree $k$ of the map correspond to vertices of degree $k$ of the tree. As special cases we recover several known bijections for bipartite maps, loopless triangulations, simple triangulations, simple quadrangulations, etc. Our work unifies and greatly extends these bijective constructions. In terms of counting, we obtain for each integer $d$ an expression for the generating function $F_d(x_d,x_{d+1},x_{d+2},\mathrm{...})$ of plane maps of girth $d$ with root-face of degree $d$, where the variable $x_k$ counts the non-root faces of degree $k$. The expression for $F_1$ was already obtained bijectively by Bouttier, Di Francesco and Guitter, but for $dgeq2$ the expression of $F_d$ is new. We also obtain an expression for the generating function $G_{p,q}^{(d,e)}(x_d,x_{d+1},\mathrm{...})$ of annular maps with root-faces of degrees $p$ and $q$, such that cycles separating the two root-faces have length at least $e$ while other cycles have length at least $d$. Our strategy is to obtain all the bijections as specializations of a single "master bijection" introduced by the authors in a previous article. In order to use this approach, we exhibit certain "canonical orientations" characterizing maps with prescribed girth constraints.

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

Recommendations

• Unified bijections for planar hypermaps with general cycle-length constraints
• A unified bijective method for maps: application to two classes with boundaries
• A bijection for nonorientable general maps
• A bijection for nonorientable general maps
• Bijections for planar maps with boundaries
• Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth
• A new family of bijections for planar maps
• A new family of bijections for planar maps
• scientific article; zbMATH DE number 596352
• A Bijection for Rooted Maps on Orientable Surfaces

zbMATH Keywords

countingplanar mapsmaster bijection

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Planar maps as labeled mobiles
• Planar diagrams
• Planar Maps are Well Labeled Trees
• A Census of Planar Maps
• Bijective counting of tree-rooted maps and shuffles of parenthesis systems
• Title not available (Why is that?)
• Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees
• Optimal coding and sampling of triangulations
• Transversal structures on triangulations: A combinatorial study and straight-line drawings
• A Census of Slicings
• Polynomial equations with one catalytic variable, algebraic series and map enumeration
• The Number of Degree-Restricted Rooted Maps on the Sphere
• A Census of Planar Triangulations
• A bijection for covered maps, or a shortcut between Harer-Zagiers and Jacksons formulas
• Counting rooted maps by genus. III: Nonseparable maps
• Unified bijections for maps with prescribed degrees and girth
• A Character Theoretic Approach to Embeddings of Rooted Maps in an Orientable Surface of Given Genus
• A bijection for triangulations, quadrangulations, pentagulations, etc.
• Census of planar maps: From the one-matrix model solution to a combinatorial proof
• Schnyder decompositions for regular plane graphs and application to drawing
• Intervals in Catalan lattices and realizers of triangulations
• Les hypercartes planaires sont des arbres très bien étiquetés. (Planar hypermaps are well-labeled trees)
• A bijection for triangulations of a polygon with interior points and multiple edges
• On the number of intervals in Tamari lattices
• Blocked edges on Eulerian maps and mobiles: application to spanning trees, hard particles and the Ising model
• Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling

Cited In (22)

• Blossoming bijection for higher-genus maps
• A note on irreducible maps with several boundaries
• Unified bijections for maps with prescribed degrees and girth
• A bijection for triangulations, quadrangulations, pentagulations, etc.
• Compact Brownian surfaces
• Topological recursion for Orlov-Scherbin tau functions, and constellations with internal faces
• Bijections for planar maps with boundaries
• Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth
• Bijective proof of the rationality of the generating series of higher-genus maps
• On polynomials counting essentially irreducible maps
• A Schnyder-type drawing algorithm for 5-connected triangulations
• Growing uniform planar maps face by face
• A simple formula for the series of constellations and quasi-constellations with boundaries
• Irreducible metric maps and Weil-Petersson volumes
• What is a random surface?
• Percolation on Triangulations: A Bijective Path to Liouville Quantum Gravity
• Bijective enumeration of planar bipartite maps with three tight boundaries, or how to slice pairs of pants
• On Irreducible Maps and Slices
• A generic method for bijections between blossoming trees and planar maps
• A bijection for essentially 4-connected toroidal triangulations
• Title not available (Why is that?)
• A bijection for rooted maps on general surfaces

This page was built for publication: Unified bijections for maps with prescribed degrees and girth

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