On Irreducible Maps and Slices

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 obtai...

Full description

Saved in:
Bibliographic Details
Published in:Combinatorics, probability & computing probability & computing, 2014-11, Vol.23 (6), p.914-972
Main Authors: BOUTTIER, J., GUITTER, E.
Format: Article
Language:English
Subjects:
Boundaries
Combinatorial analysis
Combinatorics
Cutting
Equivalence
Hierarchies
Mathematical analysis
Mathematical Physics
Mathematics
Physics
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0963-5483
1469-2163
DOI:10.1017/S0963548314000340