Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-23T23:52:02.606Z 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: [email protected], [email protected]) 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: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

Primary 05C10Secondary 05C3005A19
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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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