Smallest Percolating Sets in Bootstrap Percolation on Grids
| Autor: | Thomas Shelton, Michał Przykucki |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Bootstrap percolation
Applied Mathematics Grid Condensed Matter::Disordered Systems and Neural Networks Theoretical Computer Science Combinatorics Mathematics::Probability Computational Theory and Mathematics FOS: Mathematics Condensed Matter::Statistical Mechanics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) Geometry and Topology Constant (mathematics) Mathematics |
| Zdroj: | The Electronic Journal of Combinatorics. 27 |
| ISSN: | 1077-8926 |
| Popis: | In this paper we fill in a fundamental gap in the extremal bootstrap percolation literature, by providing the first proof of the fact that for all $d \geq 1$, the size of the smallest percolating sets in $d$-neighbour bootstrap percolation on $[n]^d$, the $d$-dimensional grid of size $n$, is $n^{d-1}$. Additionally, we prove that such sets percolate in time at most $c_d n^2$, for some constant $c_d >0 $ depending on $d$ only. 11 pages, 3 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|