Weakly saturated random graphs

Bartha, Zsolt and Kolesnik, Brett (2024) Weakly saturated random graphs. RANDOM STRUCTURES & ALGORITHMS, First. ISSN 1042-9832

Preview

Text RandomStructAlgorithms-2024-Bartha-Weaklysaturatedrandomgraphs1.pdf Available under License Creative Commons Attribution. Download (1MB) | Preview

Abstract

As introduced by Bollobás, a graph (Formula presented.) is weakly (Formula presented.) -saturated if the complete graph (Formula presented.) is obtained by iteratively completing copies of (Formula presented.) minus an edge. For all graphs (Formula presented.), we obtain an asymptotic lower bound for the critical threshold (Formula presented.), at which point the Erdős–Rényi graph (Formula presented.) is likely to be weakly (Formula presented.) -saturated. We also prove an upper bound for (Formula presented.), for all (Formula presented.) which are, in a sense, strictly balanced. In particular, we improve the upper bound by Balogh, Bollobás, and Morris for (Formula presented.), and we conjecture that this is sharp up to constants.

Actions (login required)

Edit Item