Enumeration of planar bipartite tight irreducible maps

Abstract

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)}$.

54 pages, 21 figures