Sharp Fuss-Catalan thresholds in graph bootstrap percolation
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911311165652992 |
|---|---|
| author | Bartha, Zsolt Kolesnik, Brett Kronenberg, Gal Peled, Yuval |
| author_facet | Bartha, Zsolt Kolesnik, Brett Kronenberg, Gal Peled, Yuval |
| contents | 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 (γ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 \ge 5$, such connections break down, and the process exhibits much richer behavior. The constants $λ=λ(r)$ and $γ=γ(r)$ in $p_c$ are determined by a class of $\left({r\choose2}-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26724 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sharp Fuss-Catalan thresholds in graph bootstrap percolation Bartha, Zsolt Kolesnik, Brett Kronenberg, Gal Peled, Yuval Probability Combinatorics 05C05, 05C35, 05C65, 05C80, 60K35, 68Q80 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 (γ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 \ge 5$, such connections break down, and the process exhibits much richer behavior. The constants $λ=λ(r)$ and $γ=γ(r)$ in $p_c$ are determined by a class of $\left({r\choose2}-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. |
| title | Sharp Fuss-Catalan thresholds in graph bootstrap percolation |
| topic | Probability Combinatorics 05C05, 05C35, 05C65, 05C80, 60K35, 68Q80 |
| url | https://arxiv.org/abs/2510.26724 |