Sharp Fuss-Catalan thresholds in graph bootstrap percolation

Abstract

We study graph bootstrap percolation on the Erdős-Rényi random graph ${\mathcal{G}}_{n,p}$. For all $r\ge 5$, we locate the sharp $K_r$-percolation threshold $p_c\sim ({\hat{I}}^{3}n{)}^{-1/\hat{I}»}$, solving a problem of Balogh, Bollobás and Morris. The case $r=3$ is the classical graph connectivity threshold, and the threshold for $r=4$ was found using strong connections with the well-studied $2$-neighbor dynamics from statistical physics. When $r\ge 5$, such connections break down, and the process exhibits much richer behavior. The constants $\hat{I}»=\hat{I}»(r)$ and ${\hat{I}}^3={\hat{I}}^3(r)$ in $p_c$ are determined by a class of $\left(\left(\genfrac{}{}{0ex}{}{r}{2}\right)-1\right)$-ary tree-like graphs, which we call $K_r$-tree witness graphs. These graphs are associated with the most efficient ways of adding a new edge in the $K_r$-dynamics, and they can be counted using the Fuss-Catalan numbers. Also, in the subcritical setting, we determine the asymptotic number of edges added to ${\mathcal{G}}_{n,p}$, showing that the edge density increases only by a constant factor, whose value we identify.

v2: Corrected typos. Added references, more details in Sec. 6, and a new Fig. 3. Results unchanged