Combinatorial Theory

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