Using polynomials to find lower bounds for $r$-bond bootstrap percolation
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910679401758720 |
|---|---|
| author | Morrison, Natasha Ogden, Shannon |
| author_facet | Morrison, Natasha Ogden, Shannon |
| contents | The $r$-bond bootstrap percolation process on a graph $G$ begins with a set $S$ of infected edges of $G$ (all other edges are healthy). At each step, a healthy edge becomes infected if at least one of its endpoints is incident with at least $r$ infected edges (and it remains infected). If $S$ eventually infects all of $E(G)$, we say $S$ percolates. In this paper we provide recursive formulae for the minimum size of percolating sets in several large families of graphs. We utilise an algebraic method introduced by Hambardzumyan, Hatami, and Qian, and substantially extend and generalise their work. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_24130 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Using polynomials to find lower bounds for $r$-bond bootstrap percolation Morrison, Natasha Ogden, Shannon Combinatorics The $r$-bond bootstrap percolation process on a graph $G$ begins with a set $S$ of infected edges of $G$ (all other edges are healthy). At each step, a healthy edge becomes infected if at least one of its endpoints is incident with at least $r$ infected edges (and it remains infected). If $S$ eventually infects all of $E(G)$, we say $S$ percolates. In this paper we provide recursive formulae for the minimum size of percolating sets in several large families of graphs. We utilise an algebraic method introduced by Hambardzumyan, Hatami, and Qian, and substantially extend and generalise their work. |
| title | Using polynomials to find lower bounds for $r$-bond bootstrap percolation |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.24130 |