Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth

DOI10.1016/J.JCTA.2020.105270zbMATH Open1442.05013arXiv1807.00522OpenAlexW3029983891MaRDI QIDQ778701FDOQ778701

Benjamin Lévêque, Éric Fusy

Publication date: 3 July 2020

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

Abstract: We present unified bijections for maps on the torus with control on the face-degrees and essential girth (girth of the periodic planar representation). A first step is to show that for d>=3 every toroidal d-angulation of essential girth d can be endowed with a certain "canonical" orientation (formulated as a weight-assignment on the half-edges). Using an adaptation of a construction by Bernardi and Chapuy, we can then derive a bijection between face-rooted toroidal d-angulations of essential girth d (with the condition that, apart from the root-face contour, no other closed walk of length d encloses the root-face) and a family of decorated unicellular maps. The orientations and bijections can then be generalized, for any d>=1, to toroidal face-rooted maps of essential girth d with a root-face of degree d (and with the same root-face contour condition as for d-angulations), and they take a simpler form in the bipartite case, as a parity specialization. On the enumerative side we obtain explicit algebraic expressions for the generating functions of rooted essentially simple triangulations and bipartite quadrangulations on the torus. Our bijective constructions can be considered as toroidal counterparts of those obtained by Bernardi and the first author in the planar case, and they also build on ideas introduced by Despr'e, Gonc{c}alves and the second author for essentially simple triangulations, of imposing a balancedness condition on the orientations in genus 1.

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

Recommendations

• A bijection for essentially 3-connected toroidal maps
• Unified bijections for maps with prescribed degrees and girth
• A bijection for triangulations, quadrangulations, pentagulations, etc.
• New bijective links on planar maps via orientations
• Bijections for planar maps with boundaries

zbMATH Keywords

generating functionsorientationsbijections\(d\)-angulationsgirth constraintstoroidal maps

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15)

Cites Work

• Planar maps as labeled mobiles
• Planar Maps are Well Labeled Trees
• A Census of Planar Maps
• Bijective counting of tree-rooted maps and shuffles of parenthesis systems
• Lattice structures from planar graphs
• A bijection for nonorientable general maps
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees
• A Bijection for Rooted Maps on Orientable Surfaces
• Optimal coding and sampling of triangulations
• Transversal structures on triangulations: A combinatorial study and straight-line drawings
• Polynomial equations with one catalytic variable, algebraic series and map enumeration
• Generating functions of bipartite maps on orientable surfaces
• Asymptotic Enumeration of Constellations and Related Families of Maps on Orientable Surfaces
• Counting surfaces. CRM Aisenstadt chair lectures
• A Census of Planar Triangulations
• A bijection for covered maps, or a shortcut between Harer-Zagiers and Jacksons formulas
• The asymptotic number of rooted maps on a surface
• On Irreducible Maps and Slices
• Unified bijections for maps with prescribed degrees and girth
• A bijection for triangulations, quadrangulations, pentagulations, etc.
• Les hypercartes planaires sont des arbres très bien étiquetés. (Planar hypermaps are well-labeled trees)
• Unified bijections for planar hypermaps with general cycle-length constraints
• Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling
• Bijections for planar maps with boundaries
• A generic method for bijections between blossoming trees and planar maps
• A bijection for rooted maps on general surfaces
• Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations
• Orienting triangulations
• Encoding toroidal triangulations
• A bijection for essentially 4-connected toroidal triangulations
• Blossoming bijection for higher-genus maps

Cited In (3)

• Unified bijections for maps with prescribed degrees and girth
• On polynomials counting essentially irreducible maps
• A bijection for essentially 3-connected toroidal maps

This page was built for publication: Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth

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