Weakly saturated random graphs

MaRDI QIDQ6346086zbMATH OpenFDO

Authors Zsolt Bartha, Brett Kolesnik

Publication date 29 July 2020

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Percolation (82B43)

Abstract: As introduced by Bollob'as (1967), a graph $G$ is weakly $H$-saturated if the complete graph is obtained by iteratively completing copies of $H$ minus an edge. We locate, up to multiplicative constant factors, the critical threshold $p_c$ at which point it becomes likely that the ErdH{o}s--R'enyi graph ${mathcalG}_{n,p}$ is weakly $K_r$-saturated, solving an open problem of Balogh, Bollob'as and Morris (2012). We also establish a general asymptotic lower bound for $p_c$, which holds for all graphs $H$, and more precise bounds when $H$ is balanced in a certain sense.

This page was built for publication: Weakly saturated random graphs

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