On Irreducible Maps and Slices. (November 2014)

• Record Type: Journal Article
• Authors: BOUTTIER, J.; GUITTER, E.; Broutin, Nicolas; Fill, James Allen; Nebel, Markus; Ward, Mark Daniel
• Is Part Of: Combinatorics, probability and computing. Volume 23:Number 6(2014:Nov.)
• Page Start: 914
• Page End: 972
• Publication Date: 2014-11
• Subjects: Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000340
• Languages: English
• ISSNs: 0963-5483

Abstract

<abstract abstract-type="normal"> <title> <x content-type="archive" xml:space="preserve">Abstract</x> </title> <p>We consider the problem of enumerating <italic>d</italic>-irreducible maps, <italic>i.e.</italic>, planar maps all of whose cycles have length at least <italic>d</italic>, and such that any cycle of length <italic>d</italic> is the boundary of a face of degree <italic>d</italic>. We develop two approaches in parallel: the natural approach via substitution, where these maps are obtained from general maps by a replacement of all <italic>d</italic>-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 <italic>d</italic>-irreducible maps with controlled face degrees, summarized in some elegant 'pointing formula'. We provide an equivalent description of <italic>d</italic>-irreducible slices in terms of so-called <italic>d</italic>-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.</p> </abstract>