Cut Vertices in Random Planar Maps

DOI10.4230/LIPICS.AOFA.2020.10MaRDI QIDQ6366410arXivFDO

Authors Michael Drmota, Marc Noy, Benedikt Stufler

Publication date 29 April 2021

Published in arXiv

Full work available at URL https://doi.org/10.4230/LIPICS.AOFA.2020.10

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

arXiv classification

math.CO math.PR

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

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