Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-09T11:22:30.128Z Has data issue: false hasContentIssue false
  • English
  • Français

On Irreducible Maps and Slices

Published online by Cambridge University Press:  09 July 2014

J. BOUTTIER  and
E. GUITTER
J. BOUTTIER
Affiliation:
Institut de Physique Théorique, CEA, IPhT, F-91191 Gif-sur-Yvette, France, CNRS, URA 2306 (e-mails: jeremie.bouttier@cea.fr, emmanuel.guitter@cea.fr) Département de Mathématiques et Applications, École Normale Supérieure, 45 Rue d'Ulm, F-75231 Paris Cedex 05
E. GUITTER
Affiliation:
Institut de Physique Théorique, CEA, IPhT, F-91191 Gif-sur-Yvette, France, CNRS, URA 2306 (e-mails: jeremie.bouttier@cea.fr, emmanuel.guitter@cea.fr)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Keywords

Primary 05C10Secondary 05C3005A19

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 6: Honouring the Memory of Philippe Flajolet - Part 2 , November 2014 , pp. 914 - 972
Copyright
Copyright © Cambridge University Press 2014 

References

[1]Akemann, G., Baik, J. and Di Francesco, P., eds (2011) The Oxford Handbook of Random Matrix Theory, Oxford University Press.Google Scholar
[2]Albenque, M. and Bouttier, J. (2012) Constellations and multicontinued fractions: Application to Eulerian triangulations. In 24th International Conference on Formal Power Series and Algebraic Combinatorics: FPSAC 2012, DMTCS proc. AR 805–816.Google Scholar
[3]Albenque, M., Fusy, É. and Poulalhon, D. (2014) On symmetric quadrangulations and triangulations. European J. Combin. 35 13–31.Google Scholar
[4]Albenque, M. and Poulalhon, D. (2013) Generic method for bijections between blossoming trees and planar maps. arXiv:1305.1312Google Scholar
[5]Banderier, C., Flajolet, P., Schaeffer, G. and Soria, M. (2001) Random maps, coalescing saddles, singularity analysis, and Airy phenomena. Random Struct. Alg. 19 194–246.CrossRefGoogle Scholar
[6]Bernardi, O. and Fusy, É. (2012) A bijection for triangulations, quadrangulations, pentangulations, etc. J. Combin. Theory Ser. A 119 218–244.Google Scholar
[7]Bernardi, O. and Fusy, É. (2012) Unified bijections for maps with prescribed degrees and girth. J. Combin. Theory Ser. A 119 1351–1387.Google Scholar
[8]Bousquet-Mélou, M. (2006) Limit laws for embedded trees: Applications to the integrated super-Brownian excursion. Random Struct. Alg. 29 475–523.CrossRefGoogle Scholar
[9]Bouttier, J., Di Francesco, P. and Guitter, E. (2003) Geodesic distance in planar graphs. Nucl. Phys. B663 [FS] 535–567.Google Scholar
[10]Bouttier, J. and Guitter, E. (2009) Distance statistics in quadrangulations with a boundary, or with a self-avoiding loop. J. Phys. A 42 465–208.Google Scholar
[11]Bouttier, J. and Guitter, E. (2010) Distance statistics in quadrangulations with no multiple edges and the geometry of minbus. J. Phys. A 43 205–207.Google Scholar
[12]Bouttier, J. and Guitter, E. (2012) Planar maps and continued fractions. Commun. Math. Phys. 309 623–662.CrossRefGoogle Scholar
[13]Bouttier, J. and Guitter, E.A note on irreducible maps with several boundaries. Electron. J. Combin. 21 #P1.23.Google Scholar
[14]Brown, W. G. (1965) Enumeration of quadrangular dissections of the disk. Canad. J. Math. 17 302–317.CrossRefGoogle Scholar
[15]Collet, G. and Fusy, É. (2012) . In 24th International Conference on Formal Power Series and Algebraic Combinatorics: FPSAC 2012, DMTCS proc. AR 607–618.Google Scholar
[16]Comtet, L. (1974) Advanced Combinatorics: The Art of Finite and Infinite Expansions, Springer.CrossRefGoogle Scholar
[17]Di Francesco, P. (2005) Geodesic distance in planar graphs: An integrable approach. Ramanujan J. 10 153–186.CrossRefGoogle Scholar
[18]Di Francesco, P. and Guitter, E. (2005) Integrability of graph combinatorics via random walks and heaps of dimers. J. Statist. Mech. P09001.Google Scholar
[19]Flajolet, P. (1980) Combinatorial aspects of continued fractions. Discrete Math. 32 125–161. Reprinted in the 35th Special Anniversary Issue of Discrete Math. 306 (10/11) 992–1021 (2006).Google Scholar
[20]Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.CrossRefGoogle Scholar
[21]Fusy, É. (2009) Transversal structures on triangulations: A combinatorial study and straight-line drawings. Discrete Math. 309 1870–1894.CrossRefGoogle Scholar
[22]Fusy, É. (2010) New bijective links on planar maps via orientations. European J. Combin. 31 145–160.CrossRefGoogle Scholar
[23]Fusy, É., Poulalhon, D. and Schaeffer, G. (2008) Dissections, orientations, and trees, with applications to optimal mesh encoding and to random sampling. Trans. Algorithms 4 #19.Google Scholar
[24]Goulden, I. P. and Jackson, D. M. (1983) Combinatorial Enumeration, Wiley. Republished by Dover (2004).Google Scholar
[25]Goulden, I. P. and Jackson, D. M. (2008) The KP hierarchy, branched covers, and triangulations. Adv. Math. 219 932–951.Google Scholar
[26]Kuba, M. (2011) A note on naturally embedded ternary trees. Electron J. Combin. 18 #142.CrossRefGoogle Scholar
[27]Le Gall, J.-F. (2013) Uniqueness and universality of the Brownian map. Ann. Probab. 41 2880–2960.CrossRefGoogle Scholar
[28]Mullin, R. and Schellenberg, P. (1968) The enumeration of c-nets via quadrangulations. J. Combin. Theory 4 259–276.CrossRefGoogle Scholar
[29]Schaeffer, G. (1998) Conjugaison d'arbres et cartes combinatoires aléatoires. PhD Thesis, Université Bordeaux I.Google Scholar
[30]Tutte, W. T. (1962) A census of planar triangulations. Canad. J. Math. 14 21–38.Google Scholar
[31]Tutte, W. T. (1962) A census of Hamiltonian polygons. Canad. J. Math. 14 402–417.Google Scholar
[32]Tutte, W. T. (1962) A census of slicings. Canad. J. Math. 14 708–722.CrossRefGoogle Scholar
[33]Tutte, W. T. (1963) A census of planar maps. Canad. J. Math. 15 249–271.CrossRefGoogle Scholar
[34]Viennot, X. G. (1984) Une théorie combinatoire des polynômes orthogonaux. Lecture Notes UQAM, publication du LACIM, Université du Québec à Montréal, revised (1991).Google Scholar