Enumeration of planar bipartite tight irreducible maps
Combinatorial Theory · 2026
DOI: 10.5070/c6.69945 ↗Kurz gefasst
Fachartikel in der Zeitschrift Combinatorial Theory, 2026. Verfasst von Jérémie Bouttier und 2 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
We consider planar bipartite maps which are both tight, i.e. without vertices of degree \(1\), and \(2b\)-irreducible, i.e. such that each cycle has length at least \(2b\) and such that any cycle of length exactly \(2b\) is the contour of a face. It was shown by Budd that the number \(\mathcal N_n^{(b)}\) of such maps made out of a fixed set of \(n\) faces with prescribed even degrees is a polynomial in both \(b\) and the face degrees. In this paper, we give an explicit expression for \(\mathcal N_n^{(b)}\) by a direct bijective approach based on the so-called slice decomposition. More precisely, we decompose any of the maps at hand into a collection of \(2b\)-irreducible tight slices and a suitable two-face map. We show how to bijectively encode each \(2b\)-irreducible slice via a \(b\)-decorated tree drawn on its derived map, and how to enumerate collections thereof. We then discuss the polynomial counting of two-face maps, and show how to combine it with the former enumeration to obtain \(\mathcal N_n^{(b)}\). Mathematics Subject Classifications: 05A15, 05A19 Keywords: Planar maps, bijective enumeration, slice decomposition
Zitieren
APA
Bouttier, J., Guitter, E., & Manet, H. (2026). Enumeration of planar bipartite tight irreducible maps. Combinatorial Theory. https://doi.org/10.5070/c6.69945
Vancouver
Bouttier J, Guitter E, Manet H. Enumeration of planar bipartite tight irreducible maps. Combinatorial Theory. 2026. doi:10.5070/c6.69945
BibTeX
@article{Bouttier2026,
author = {Bouttier, Jérémie and Guitter, Emmanuel and Manet, Hugo},
title = {Enumeration of planar bipartite tight irreducible maps},
journal = {Combinatorial Theory},
year = {2026},
doi = {10.5070/c6.69945}
}
EUVIMED