Maps of unfixed genus and blossoming trees

DOI10.1016/J.AAM.2021.102208zbMATH Open1468.05011arXiv2003.00885OpenAlexW3159656819MaRDI QIDQ2040990FDOQ2040990

Éric Fusy, Emmanuel Guitter

Publication date: 15 July 2021

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: We introduce bijections between families of rooted maps with unfixed genus and families of so-called blossoming trees endowed with an arbitrary forward matching of their leaves. We first focus on Eulerian maps with controlled vertex degrees. The mapping from blossoming trees to maps is a generalization to unfixed genus of Schaeffer's closing construction for planar Eulerian maps. The inverse mapping relies on the existence of canonical orientations which allow to equip the maps with canonical spanning trees, as proved by Bernardi. Our bijection gives in particular (here in the Eulerian case) a combinatorial explanation to the striking similarity between the (infinite) recursive system of equations which determines the partition function of maps with unfixed genus (as obtained via matrix models and orthogonal polynomials) and that determining the partition function of planar maps. All the functions in the recursive system get a combinatorial interpretation as generating functions for maps endowed with particular multiple markings of their edges. This allows us in particular to give a combinatorial proof of some differential identities satisfied by these functions. We also consider face-colored Eulerian maps with unfixed genus and derive some striking identities between their generating functions and those of properly weighted marked maps. The same methodology is then applied to deal with $m$-regular bipartite maps with unfixed genus, leading to similar results. The case of cubic maps is also briefly discussed.

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

zbMATH Keywords

canonical spanning treesEulerian maps with controlled vertex degrees

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geodesic distance in planar graphs
• Planar maps as labeled mobiles
• Handbook of Enumerative Combinatorics
• A Census of Planar Maps
• Planar maps and continued fractions
• Bijective counting of tree-rooted maps and shuffles of parenthesis systems
• Quantum field theory techniques in graphical enumeration
• Lattice structures from planar graphs
• Graphs on surfaces
• Graphs on surfaces and their applications. Appendix by Don B. Zagier
• The Euler characteristic of the moduli space of curves
• Combinatorial aspects of continued fractions
• 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
• A Census of Slicings
• Asymptotic Enumeration of Constellations and Related Families of Maps on Orientable Surfaces
• Rational and algebraic series in combinatorial enumeration
• Counting surfaces. CRM Aisenstadt chair lectures
• A Census of Planar Triangulations
• A simple model of trees for unicellular maps
• A direct bijection for the Harer-Zagier formula
• Enumeration of planar constellations
• An analogue of the Harer-Zagier formula for unicellular maps on general surfaces
• Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings
• A bijection for triangulations, quadrangulations, pentagulations, etc.
• Census of planar maps: From the one-matrix model solution to a combinatorial proof
• A generic method for bijections between blossoming trees and planar maps
• Walks on the slit plane
• Annular embeddings of permutations for arbitrary genus
• Blossoming bijection for higher-genus maps
• Rooted maps on orientable surfaces, Riccati's equation and continued fractions
• Continued fraction solutions of the Riccati equation

This page was built for publication: Maps of unfixed genus and blossoming trees

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