Explosive appearance of cores and bootstrap percolation on lattices
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_ | 1866908780142264320 |
|---|---|
| author | Hartarsky, Ivailo Lichev, Lyuben |
| author_facet | Hartarsky, Ivailo Lichev, Lyuben |
| contents | Consider the process where the $n$ vertices of a square $2$-dimensional torus appear consecutively in a random order. We show that typically the size of the $3$-core of the corresponding induced unit-distance graph transitions from $0$ to $n-o(n)$ within a single step. Equivalently, by infecting the vertices of the torus in a random order, under two-neighbour bootstrap percolation, the size of the infected set transitions instantaneously from $o(n)$ to $n$. This hitting time result answers a question of Benjamini.
We also study the much more challenging and general setting of bootstrap percolation on two-dimensional lattices for a variety of finite-range infection rules. In this case, powerful but fragile bootstrap percolation tools such as the rectangles process and the Aizenman-Lebowitz lemma become unavailable. We develop a new method complementing and replacing these standard techniques, thus allowing us to prove the above hitting time result for a wide family of threshold bootstrap percolation rules on the $2$-dimensional square lattice, including neighbourhoods given by large $\ell^p$ balls for $p\in[1,\infty]$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_18976 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Explosive appearance of cores and bootstrap percolation on lattices Hartarsky, Ivailo Lichev, Lyuben Combinatorics Probability 05C69, 05C80, 60C05, 60K35 Consider the process where the $n$ vertices of a square $2$-dimensional torus appear consecutively in a random order. We show that typically the size of the $3$-core of the corresponding induced unit-distance graph transitions from $0$ to $n-o(n)$ within a single step. Equivalently, by infecting the vertices of the torus in a random order, under two-neighbour bootstrap percolation, the size of the infected set transitions instantaneously from $o(n)$ to $n$. This hitting time result answers a question of Benjamini. We also study the much more challenging and general setting of bootstrap percolation on two-dimensional lattices for a variety of finite-range infection rules. In this case, powerful but fragile bootstrap percolation tools such as the rectangles process and the Aizenman-Lebowitz lemma become unavailable. We develop a new method complementing and replacing these standard techniques, thus allowing us to prove the above hitting time result for a wide family of threshold bootstrap percolation rules on the $2$-dimensional square lattice, including neighbourhoods given by large $\ell^p$ balls for $p\in[1,\infty]$. |
| title | Explosive appearance of cores and bootstrap percolation on lattices |
| topic | Combinatorics Probability 05C69, 05C80, 60C05, 60K35 |
| url | https://arxiv.org/abs/2501.18976 |