LIPIcs.AofA.2018.19.pdf
- Filesize: 0.64 MB
- 18 pages
Document
The Number of Double Triangles in Random Planar Maps
Authors
Michael Drmota 
,
-
Part of:
Volume:
29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-18
File
Document Identifiers
Author Details
Cite AsGet BibTex
Michael Drmota and Guan-Ru Yu. The Number of Double Triangles in Random Planar Maps. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.AofA.2018.19
https://doi.org/10.4230/LIPIcs.AofA.2018.19
Abstract
The purpose of this paper is to provide a central limit theorem for the number of occurrences of double triangles in random planar maps. This is the first result of this kind that goes beyond face counts of given valency. The method is based on generating functions, an involved combinatorial decomposition scheme that leads to a system of catalytic functional equations and an analytic extension of the Quadratic Method to systems of equations.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Enumeration
- Mathematics of computing → Graph enumeration
Keywords
- Planar maps
- pattern occuence
- generating functions
- quadratic method
- central limit theorem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- O. Angel and O. Schramm. Uniform infinite planar triangulations. Commun. Math. Phys., 241(2-3):191-213, 2003. URL: http://dx.doi.org/10.1007/s00220-003-0932-3.
- M. Bousquet-Mélou and A. Jehanne. Polynomial equations with one catalytic variable, algebraic series and map enumeration. J. Comb. Theory, Ser. B, 96(5):623-672, 2006. URL: http://dx.doi.org/10.1016/j.jctb.2005.12.003.
- W.G. Brown and W.T. Tutte. On the enumeration of rooted non-separable planar maps. Can. J. Math., 16:572-577, 1964. URL: http://dx.doi.org/10.4153/CJM-1964-058-7.
-
G. Collet, M. Drmota, and L. Klausner. Limit Laws of Planar Maps with Prescribed Vertex Degrees. Combinatorics Probability Computing, to appear.
- M. Drmota. Random trees. An interplay between combinatorics and probability. Wien: Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-211-75357-6.
-
M. Drmota and M. Noy. Universal exponents and tail estimates in the enumeration of planar maps. In Extended abstracts of the sixth European conference on combinatorics, graph theory and applications, EuroComb 2011, Budapest, Hungary, August 29 - September 2, 2011, pages 309-317. Amsterdam: Elsevier, 2011.
- M. Drmota and K. Panagiotou. A central limit theorem for the number of degree-k vertices in random maps. Algorithmica, 66(4):741-761, 2013. URL: http://dx.doi.org/10.1007/s00453-013-9751-x.
-
M. Drmota and B. Stufler. Benjamini-schramm convergence of random planar maps. arXiv preprint arXiv:1801.10007, 2018.
- Z. Gao and N. C. Wormald. Asymptotic normality determined by high moments, and submap counts of random maps. Probab. Theory Relat. Fields, 130(3):368-376, 2004. URL: http://dx.doi.org/10.1007/s00440-004-0356-9.
-
M. Krikun. Local structure of random quadrangulations. arXiv preprint math/0512304, 2005.
- R. Stephenson. Local convergence of large critical multi-type Galton-Watson trees and applications to random maps. J. Theor. Probab., 31(1):159-205, 2018. URL: http://dx.doi.org/10.1007/s10959-016-0707-3.
- W. T. Tutte. A census of planar maps. Can. J. Math., 15:249-271, 1963. URL: http://dx.doi.org/10.4153/CJM-1963-029-x.