On Irreducible Maps and Slices

Source abstract

We consider the problem of enumerating d -irreducible maps, i.e. , planar maps all of whose cycles have length at least d , and such that any cycle of length d is the boundary of a face of degree d . We develop two approaches in parallel: the natural approach via substitution, where these maps are obtained from general maps by a replacement of all d -cycles by elementary faces, and a bijective approach via slice decomposition, which consists in cutting the maps along shortest paths. Both lead to explicit expressions for the generating functions of d -irreducible maps with controlled face degrees, summarized in some elegant ‘pointing formula’. We provide an equivalent description of d -irreducible slices in terms of so-called d -oriented trees. We finally show that irreducible maps give rise to a hierarchy of discrete integrable equations which include equations encountered previously in the context of naturally embedded trees.