Sharp Fuss-Catalan thresholds in graph bootstrap percolation

Start with an Erdős–Rényi random graph G(n,p), and repeatedly add a missing edge whenever its addition completes a copy of K_r, a clique of size r. Balogh, Bollobás and Morris asked: how large must p so that, with high probability, this process produces the complete graph?

For r=3, this is precisely the classical Erdős–Rényi connectivity problem. The case r=4 was resolved by Angel and Kolesnik and is closely related to two-neighbor bootstrap percolation.

I will present the sharp percolation threshold for every fixed r≥5. In this regime, a different mechanism governs the transition: the critical probability is determined by certain “tree witness graphs,” which encode the most efficient ways of adding an edge. The enumeration of these graphs leads to the Fuss–Catalan numbers.

Joint work with Zsolt Bartha, Brett Kolesnik and Gal Kronenberg.