2025/10/30 by Bartha, Zsolt, Kolesnik, Brett, Kronenberg, Gal +1
#05C05 #05C35 #05C65 #05C80 #60K35 #68Q80 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2510.26724
We study graph bootstrap percolation on the Erdős-Rényi random graph \mathcal Gn,p. For all r ≥ 5, we locate the sharp Kr-percolation threshold pc ∼ (γn)-1/λ, 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 ≥ 5, such connections break down, and the process exhibits much richer behavior. The constants λ=λ(r) and γ=γ(r) in pc are determined by a class of (r\choose2-1)-ary tree-like graphs, which we call Kr-tree witness graphs. These graphs are associated with the most efficient ways of adding a new edge in the Kr-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 Gn,p, showing that the edge density increases only by a constant factor, whose value we identify.