Document Open Access Logo

Asymptotic Distribution of Parameters in Random Maps

Authors Olivier Bodini, Julien Courtiel, Sergey Dovgal, Hsien-Kuei Hwang

PDF
Thumbnail PDF

File

LIPIcs.AofA.2018.13.pdf
  • Filesize: 0.87 MB
  • 12 pages

Document Identifiers

Author Details

Olivier Bodini
  • UMR CNRS 7030, LIPN, Université Paris 13, Av. Jean Baptiste Clément, Villetaneuse, France
Julien Courtiel
  • UMR 6072, AMACC, Université de Caen Normandie, Bd du Maréchal Juin, Caen, France
Sergey Dovgal
  • UMR CNRS 7030, LIPN, Université Paris 13, Av. Jean Baptiste Clément, Villetaneuse, France , IRIF, Université Paris 7, Rue Thomas Mann Paris, France , Moscow Institute of Physics and Technology, Institutskiy per. 9, Dolgoprudny, Russia
Hsien-Kuei Hwang
  • Institute of Statistical Science, Academia Sinica, 128, Section 2, Academia Rd, Nangang District, Taipei City, Taiwan.

Funding

This work was partially supported by the METACONC Project of ANR-MOST (2016-2019).

Cite As Get BibTex

Olivier Bodini, Julien Courtiel, Sergey Dovgal, and Hsien-Kuei Hwang. Asymptotic Distribution of Parameters in Random 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. 13:1-13:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.AofA.2018.13

Abstract

We consider random rooted maps without regard to their genus, with fixed large number of edges, and address the problem of limiting distributions for six different parameters: vertices, leaves, loops, root edges, root isthmus, and root vertex degree. Each of these leads to a different limiting distribution, varying from (discrete) geometric and Poisson distributions to different continuous ones: Beta, normal, uniform, and an unusual distribution whose moments are characterised by a recursive triangular array.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Enumeration
Keywords
  • Random maps
  • Analytic combinatorics
  • Rooted Maps
  • Beta law
  • Limit laws
  • Patterns
  • Generating functions
  • Riccati equation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Didier Arquès and Jean-François Béraud. Rooted maps on orientable surfaces, Riccati’s equation and continued fractions. Discrete mathematics, 215(1-3):1-12, 2000. Google Scholar
  2. Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, and Michele Soria. Random maps, coalescing saddles, singularity analysis, and Airy phenomena. Random Structures &Algorithms, 19(3-4):194-246, 2001. Google Scholar
  3. Edward A Bender and L.Bruce Richmond. A survey of the asymptotic behaviour of maps. Journal of Combinatorial Theory, Series B, 40(3):297-329, 1986. URL: http://dx.doi.org/10.1016/0095-8956(86)90086-9.
  4. Olivier Bernardi and Mireille Bousquet-Mélou. Counting coloured planar maps: differential equations. Communications in Mathematical Physics, 354(1):31-84, 2017. Google Scholar
  5. Olivier Bodini, Danielle Gardy, and Alice Jacquot. Asymptotics and random sampling for BCI and BCK lambda terms. Theoretical Computer Science, 502:227-238, 2013. Google Scholar
  6. Mireille Bousquet-Mélou and Arnaud Jehanne. Polynomial equations with one catalytic variable, algebraic series and map enumeration. Journal of Combinatorial Theory, Series B, 96(5):623-672, 2006. Google Scholar
  7. Ariane Carrance. Uniform random colored complexes. arXiv preprint arXiv:1705.11103, 2017. Google Scholar
  8. Robert Cori. Indecomposable permutations, hypermaps and labeled Dyck paths. Journal of Combinatorial Theory, Series A, 116(8):1326-1343, 2009. Google Scholar
  9. Julien Courtiel and Karen Yeats. Terminal chords in connected chord diagrams. Annales de l'Institut Henri Poincaré D, 4(4):417-452, 2017. Google Scholar
  10. Julien Courtiel, Karen Yeats, and Noam Zeilberger. Connected chord diagrams and bridgeless maps. arXiv preprint arXiv:1611.04611, 2016. Google Scholar
  11. Predrag Cvitanović, B. Lautrup, and Robert B. Pearson. Number and weights of Feynman diagrams. Phys. Rev. D, 18:1939-1949, Sep 1978. URL: http://dx.doi.org/10.1103/PhysRevD.18.1939.
  12. Michael Drmota and Konstantinos Panagiotou. A central limit theorem for the number of degree-k vertices in random maps. Algorithmica, 66(4):741-761, 2013. Google Scholar
  13. P. Flajolet and R. Sedgewick. Analytic combinatorics. Camb. Univ. Press, 2009. Google Scholar
  14. Philippe Flajolet and Marc Noy. Analytic combinatorics of chord diagrams. In Formal Power Series and Algebraic Combinatorics, pages 191-201. Springer, 2000. Google Scholar
  15. Hsien-Kuei Hwang. On convergence rates in the central limit theorems for combinatorial structures. European Journal of Combinatorics, 19(3):329-343, 1998. Google Scholar
  16. Hsien-Kuei Hwang. Asymptotics of poisson approximation to random discrete distributions: an analytic approach. Advances in Applied Probability, 31(2):448-491, 1999. Google Scholar
  17. Sergei K. Lando and Alexander K. Zvonkin. Graphs on Surfaces and Their Applications. Number 141 in Encyclopaedia of Mathematical Sciences. Springer-Verlag, 2004. Google Scholar
  18. Valery A Liskovets. A pattern of asymptotic vertex valency distributions in planar maps. Journal of Combinatorial Theory, Series B, 75(1):116-133, 1999. Google Scholar
  19. Andrew M Odlyzko. Asymptotic enumeration methods. Handbook of combinatorics, 2(1063-1229):1229, 1995. Google Scholar
  20. N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. URL: http://oeis.org.
  21. Noam Zeilberger and Alain Giorgetti. A correspondence between rooted planar maps and normal planar lambda terms. Logical Methods in Computer Science, 11(3:22), 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact