Cut vertices in random planar maps

DOI10.37236/11163MaRDI QIDQ6199192zbMATH OpenOpenAlexFDO

Authors Michael Drmota, Marc Noy, Benedikt Stufler

Publication date 23 February 2024

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/11163

zbMATH Keywords

central limit theoremsubcritical classes of planar maps

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial probability (60C05) Central limit and other weak theorems (60F05)

Review text

Summary: 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 \to c\) in probability (for some explicit \(c>0)\). For so-called subcritical classes of planar maps (like outerplanar maps) we obtain a central limit theorem, too. Interestingly the combinatorics behind this seemingly simple problem is quite involved.

Recommendations

• A central limit theorem for the number of degree-\(k\) vertices in random maps
• A central limit theorem for the number of degree-\(k\) vertices in random maps
• A pattern of asymptotic vertex valency distributions in planar maps
• The distribution of the number of small cuts in a random planar triangulation
• scientific article; zbMATH DE number 6297799

Cites work

• A Census of Planar Maps
• A central limit theorem for the number of degree-\(k\) vertices in random maps
• A pattern of asymptotic vertex valency distributions in planar maps
• A probabilistic approach to block sizes in random maps
• A view from infinity of the uniform infinite planar quadrangulation
• Analytic combinatorics
• Conditional distribution of heavy tailed random variables on large deviations of their sum
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• Local convergence of large critical multi-type Galton-Watson trees and applications to random maps
• Percolation on uniform infinite planar maps
• Planar maps as labeled mobiles
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• Random Trees
• Recurrence of bipartite planar maps
• Root vertex valency distributions of rooted maps and rooted triangulations
• Scaling limits of random outerplanar maps with independent link-weights
• The distribution of the number of small cuts in a random planar triangulation
• The number of double triangles in random planar maps
• Uniform infinite planar triangulations

Cited in

(1)

• Upper bounds for some graph invariants in terms of blocks and cut-vertices

This page was built for publication: Cut vertices in random planar maps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199192)