The critical activation density in graph bootstrap percolation
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914567616987136 |
|---|---|
| author | Kolesnik, Brett Makai, Tamás Nenadov, Rajko Pérez-Giménez, Xavier Prałat, Paweł Zhukovskii, Maksim |
| author_facet | Kolesnik, Brett Makai, Tamás Nenadov, Rajko Pérez-Giménez, Xavier Prałat, Paweł Zhukovskii, Maksim |
| contents | In graph bootstrap percolation, edges of an Erdős-Rényi random graph ${\mathcal G}_{n,p}$ are initially active. Activation spreads to other edges of the complete graph $K_n$ by an iterative process governed by a fixed graph $H$, whereby an edge becomes active whenever it is the only inactive edge in a copy of $H$. If all edges of $K_n$ are eventually activated, we say the process $H$-percolates. The case $H=K_3$ corresponds to the classical sharp threshold for connectivity in ${\mathcal G}_{n,p}$. When $H=K_4$, there are close connections with $2$-neighbor bootstrap percolation from statistical physics. Varying $H$ produces a wide range of behaviors.
In this work, for every graph $H$, we locate the critical $H$-percolation threshold $p_c(n,H)$, answering a question of Balogh, Bollobás, and Morris. Our general methods recover and improve several previous results. The location of $p_c(n,H)$ is related to a critical limiting density $ρ(H)$ of graphs that most efficiently activate a given edge. Introducing the parameter $ρ(H)$ raises several questions. For instance, it remains open whether $ρ(H)$ is computable in general, and its expression appears to indicate when the $H$-percolation threshold is sharp. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_15066 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The critical activation density in graph bootstrap percolation Kolesnik, Brett Makai, Tamás Nenadov, Rajko Pérez-Giménez, Xavier Prałat, Paweł Zhukovskii, Maksim Probability Combinatorics 05C35, 05C80, 82B43, 68Q80 In graph bootstrap percolation, edges of an Erdős-Rényi random graph ${\mathcal G}_{n,p}$ are initially active. Activation spreads to other edges of the complete graph $K_n$ by an iterative process governed by a fixed graph $H$, whereby an edge becomes active whenever it is the only inactive edge in a copy of $H$. If all edges of $K_n$ are eventually activated, we say the process $H$-percolates. The case $H=K_3$ corresponds to the classical sharp threshold for connectivity in ${\mathcal G}_{n,p}$. When $H=K_4$, there are close connections with $2$-neighbor bootstrap percolation from statistical physics. Varying $H$ produces a wide range of behaviors. In this work, for every graph $H$, we locate the critical $H$-percolation threshold $p_c(n,H)$, answering a question of Balogh, Bollobás, and Morris. Our general methods recover and improve several previous results. The location of $p_c(n,H)$ is related to a critical limiting density $ρ(H)$ of graphs that most efficiently activate a given edge. Introducing the parameter $ρ(H)$ raises several questions. For instance, it remains open whether $ρ(H)$ is computable in general, and its expression appears to indicate when the $H$-percolation threshold is sharp. |
| title | The critical activation density in graph bootstrap percolation |
| topic | Probability Combinatorics 05C35, 05C80, 82B43, 68Q80 |
| url | https://arxiv.org/abs/2605.15066 |