A simple path to component sizes in critical random graphs

DOI10.1137/22M151056XMaRDI QIDQ6387470zbMATH OpenOpenAlexFDO

Authors Umberto De Ambroggio

Publication date 4 January 2022

Full work available at URL https://doi.org/10.1137/22m151056x

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Combinatorial probability (60C05) Sums of independent random variables; random walks (60G50)

Abstract: We describe a robust methodology, based on the martingale argument of Nachmias and Peres and random walk estimates, to obtain simple upper and lower bounds on the size of a maximal component in several random graphs extit{at criticality}. Even though the main result is not new, we believe the the material presented here is interesting because it unifies several proofs found in the literature into a common framework. More specifically, we give easy-to-check conditions that, when satisfied, allow an immediate derivation of the above mentioned bounds.

Recommendations

• An elementary approach to component sizes in critical random graphs
• The critical random graph, with martingales
• Upper bounds for the largest component in critical inhomogeneous random graphs
• Size of the largest component in a critical graph
• On the largest component of the random graph at a nearcritical stage

Cited in

(1)

• Upper bounds for the largest component in critical inhomogeneous random graphs

This page was built for publication: A simple path to component sizes in critical random graphs

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