2024/10/11 by Jérémie Bouttier, Bouttier, Jérémie, Emmanuel Guitter +3 · 1 citation
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2410.08802
openalex publication_date 2024/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Nn(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 Nn(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 Nn(b).