Document Open Access Logo

Cut Vertices in Random Planar Maps

Authors Michael Drmota , Marc Noy , Benedikt Stufler

PDF
Thumbnail PDF

File

LIPIcs.AofA.2020.10.pdf
  • Filesize: 0.9 MB
  • 18 pages

Document Identifiers

Author Details

Michael Drmota
  • TU Wien, Institute of Discrete Mathematics and Geometry, Wiedner Hauptstrasse 8 - 10, A-1040 Vienna, Austria
Marc Noy
  • Universitat Politècnica de Catalunya, Departament de Matemàtica Aplicada II, Jordi Girona 1 - 3, 08034 Barcelona, Spain
Benedikt Stufler
  • Universität München, Mathematisches Institut, Theresienstr. 39, 80333 Munich, Germany

Funding

  • Drmota, Michael: Research supported by the Austrian Science Foundation FWF, project F50-02.
  • Noy, Marc: Research supported in part by Ministerio de Ciencia, Innovación y Universidades MTM2017-82166-P.

Acknowledgements

We thank the referees for their careful reading and their valuable comments for improving the presentation.

Cite As Get BibTex

Michael Drmota, Marc Noy, and Benedikt Stufler. Cut Vertices in Random Planar Maps. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.AofA.2020.10

Abstract

The main goal of this paper is to determine the asymptotic behavior of the number X_n of cut-vertices in random planar maps with n edges. It is shown that X_n/n → c in probability (for some explicit c>0). For so-called subcritial subclasses of planar maps like outerplanar maps we obtain a central limit theorem, too.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Random graphs
Keywords
  • random planar maps
  • cut vertices
  • generating functions
  • local graph limits

Metrics

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

References

  1. Omer Angel and Oded Schramm. Uniform infinite planar triangulations. Comm. Math. Phys., 241(2-3):191-213, 2003. URL: https://doi.org/10.1007/978-1-4419-9675-6_16.
  2. Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, and Michèle Soria. Random maps, coalescing saddles, singularity analysis, and Airy phenomena. Random Structures Algorithms, 19(3-4):194-246, 2001. Analysis of algorithms (Krynica Morska, 2000). URL: https://doi.org/10.1002/rsa.10021.
  3. Patrick Billingsley. Convergence of probability measures. Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons, Inc., New York, second edition, 1999. A Wiley-Interscience Publication. URL: https://doi.org/10.1002/9780470316962.
  4. Jakob E. Björnberg and Sigurdur Ö. Stefánsson. Recurrence of bipartite planar maps. Electron. J. Probab., 19:no. 31, 40, 2014. URL: https://doi.org/10.1214/EJP.v19-3102.
  5. J. Bouttier, P. Di Francesco, and E. Guitter. Planar maps as labeled mobiles. Electron. J. Combin., 11(1):Research Paper 69, 27, 2004. URL: http://www.combinatorics.org/Volume_11/Abstracts/v11i1r69.html.
  6. N. Curien, L. Ménard, and G. Miermont. A view from infinity of the uniform infinite planar quadrangulation. ALEA Lat. Am. J. Probab. Math. Stat., 10(1):45-88, 2013. Google Scholar
  7. Michael Drmota. Random trees. SpringerWienNewYork, Vienna, 2009. An interplay between combinatorics and probability. URL: https://doi.org/10.1007/978-3-211-75357-6.
  8. 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. URL: https://doi.org/10.1007/s00453-013-9751-x.
  9. Michael Drmota and Benedikt Stufler. Pattern occurrences in random planar maps. Statistics & Probability Letters, page 108666, 2019. URL: https://doi.org/10.1016/j.spl.2019.108666.
  10. Michael Drmota and Guan-Ru Yu. The number of double triangles in random planar maps. Proceedings AofA 2018. Leibniz International Proceedings in Informatics., 110:19:1-19:18, 2018. Google Scholar
  11. Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. Cambridge University Press, Cambridge, 2009. URL: https://doi.org/10.1017/CBO9780511801655.
  12. Zhicheng Gao and L. Bruce Richmond. Root vertex valency distributions of rooted maps and rooted triangulations. Eur. J. Comb., 15(5):483-490, 1994. Google Scholar
  13. M. Krikun. Local structure of random quadrangulations. ArXiv Mathematics e-prints, December 2005. URL: http://arxiv.org/abs/math/0512304.
  14. Valery A. Liskovets. A pattern of asymptotic vertex valency distributions in planar maps. J. Combin. Theory Ser. B, 75(1):116-133, 1999. URL: https://doi.org/10.1006/jctb.1998.1870.
  15. Laurent Ménard and Pierre Nolin. Percolation on uniform infinite planar maps. Electron. J. Probab., 19:no. 79, 27, 2014. URL: https://doi.org/10.1214/EJP.v19-2675.
  16. Robin Stephenson. Local convergence of large critical multi-type galton-watson trees and applications to random maps. Journal of Theoretical Probability, pages 1-47, 2016. URL: https://doi.org/10.1007/s10959-016-0707-3.
  17. Benedikt Stufler. Local convergence of random planar graphs. arXiv e-prints, August 2019. URL: http://arxiv.org/abs/1908.04850.
  18. Benedikt Stufler. Rerooting multi-type branching trees: the infinite spine case. arXiv e-prints, August 2019. URL: http://arxiv.org/abs/1908.04843.
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