Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-23T14:13:22.615Z Has data issue: false hasContentIssue false
  • English
  • Français

Limit laws of planar maps with prescribed vertex degrees

Part of: Combinatorics Graph theory

Published online by Cambridge University Press:  04 February 2019

G. Collet ,
M. Drmota  and
L. D. Klausner
G. Collet
Affiliation:
TU Wien, Institute of Discrete Mathematics and Geometry, Wiedner Hauptstraße 8–10, A-1040 Wien, Austria
M. Drmota*
Affiliation:
TU Wien, Institute of Discrete Mathematics and Geometry, Wiedner Hauptstraße 8–10, A-1040 Wien, Austria
L. D. Klausner
Affiliation:
TU Wien, Institute of Discrete Mathematics and Geometry, Wiedner Hauptstraße 8–10, A-1040 Wien, Austria
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove a generalmulti-dimensional central limit theorem for the expected number of vertices of a given degree in the family of planar maps whose vertex degrees are restricted to an arbitrary (finite or infinite) set of positive integers D. Our results rely on a classical bijection with mobiles (objects exhibiting a tree structure), combined with refined analytic tools to deal with the systems of equations on infinite variables that arise. We also discuss possible extensions to maps of higher genus and to weighted maps.

MSC classification

Primary: 05A16: Asymptotic enumeration
Secondary: 05C07: Vertex degrees 05C10: Planar graphs; geometric and topological aspects of graph theory 05C30: Enumeration in graph theory
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Special Issue 4: Analysis of Algorithms , July 2019 , pp. 519 - 541
Copyright
© Cambridge University Press 2019 

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

Footnotes

†

Partially supported by the Austrian Science Fund (FWF) project SFB F50-02 ‘Shape Characteristics of Planar Maps and Planar Graphs’.

References

Banderier, C. and Drmota, M. (2015) Formulae and asymptotics for coefficients of algebraic functions. Combin. Probab. Comput. 24 1–53.CrossRefGoogle Scholar
Bender, E. A. and Canfield, E. R. (1986) The asymptotic number of rooted maps on a surface. J. Combin. Theory Ser. A 43 244–257.CrossRefGoogle Scholar
Bender, E. A. and Canfield, E. R. (1993) Enumeration of degree restricted maps on the sphere. In Planar Graphs (Trotter, W. T., ed.), Vol. 9 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, pp. 13–16.CrossRefGoogle Scholar
Bettinelli, J. (2016) A bijection for nonorientable general maps. In 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016), DMTCS Proc. BC, pp. 227–238.Google Scholar
Bouttier, J., Di Francesco, P. and Guitter, E. (2004) Planar maps as labeled mobiles. Electron. J. Combin. 11 R69.Google Scholar
Chapuy, G. (2009) Asymptotic enumeration of constellations and related families of maps on orientable surfaces. Combin. Probab. Comput. 18 477–516.CrossRefGoogle Scholar
Chapuy, G. and Dołȩga, M. (2017) A bijection for rooted maps on general surfaces. J. Combin. Theory Ser. A 145 252–307.CrossRefGoogle Scholar
Chapuy, G., Fusy, É., Kang, M. and Shoilekova, B. (2008) A complete grammar for decomposing a family of graphs into 3-connected components. Electron. J. Combin. 15 R148.Google Scholar
Chapuy, G., Marcus, M. and Schaeffer, G. (2009) A bijection for rooted maps on orientable surfaces. SIAM J. Discrete Math 23 1587–1611.CrossRefGoogle Scholar
Collet, G. and Fusy, É. (2012) A simple formula for the series of bipartite and quasi-bipartite maps with boundaries. In 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), DMTCS Proc. AR, pp. 607–618.Google Scholar
Drmota, M. (2009) Random Trees: An Interplay Between Combinatorics and Probability, Springer.CrossRefGoogle Scholar
Drmota, M., Gittenberger, B. and Morgenbesser, J. F. (2012) Infinite systems of functional equations and Gaussian limiting distributions. In 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods in the Analysis of Algorithms (AofA ’12), DMTCS Proc. AQ, pp. 453–478.Google Scholar
Drmota, M. and Panagiotou, K. (2013) A central limit theorem for the number of degree-k vertices in random maps. Algorithmica 66 741–761.CrossRefGoogle Scholar
Marckert, J.-F. andMiermont, G. (2007) Invariance principles for random bipartite planar maps. Ann. Probab. 35 1642–1705.CrossRefGoogle Scholar
Miermont, G. and Weil, M. (2008) Radius and profile of random planar maps with faces of arbitrary degrees. Electron. J. Probab. 13 #4, 79–106.CrossRefGoogle Scholar
Tutte, W. T. (1963) A census of planar maps. Canad. J. Math. 15 249–271.CrossRefGoogle Scholar