Linear algebra and bootstrap percolation
In $\HH$-bootstrap percolation, a set $A \subset V(\HH)$ of initially 'infected' vertices spreads by infecting vertices which are the only uninfected vertex in an edge of the hypergraph $\HH$. A particular case of this is the $H$-bootstrap process, in which $\HH$ encodes copies of $H$ in a...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2011
|
| _version_ | 1797075395850272768 |
|---|---|
| author | Balogh, J Bollobás, B Morris, R Riordan, O |
| author_facet | Balogh, J Bollobás, B Morris, R Riordan, O |
| author_sort | Balogh, J |
| collection | OXFORD |
| description | In $\HH$-bootstrap percolation, a set $A \subset V(\HH)$ of initially 'infected' vertices spreads by infecting vertices which are the only uninfected vertex in an edge of the hypergraph $\HH$. A particular case of this is the $H$-bootstrap process, in which $\HH$ encodes copies of $H$ in a graph $G$. We find the minimum size of a set $A$ that leads to complete infection when $G$ and $H$ are powers of complete graphs and $\HH$ encodes induced copies of $H$ in $G$. The proof uses linear algebra, a technique that is new in bootstrap percolation, although standard in the study of weakly saturated graphs, which are equivalent to (edge) $H$-bootstrap percolation on a complete graph. |
| first_indexed | 2024-03-06T23:49:48Z |
| format | Journal article |
| id | oxford-uuid:7238c5aa-b2e8-4f72-a37d-7d91435acfc5 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T23:49:48Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | oxford-uuid:7238c5aa-b2e8-4f72-a37d-7d91435acfc52022-03-26T19:48:37ZLinear algebra and bootstrap percolationJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7238c5aa-b2e8-4f72-a37d-7d91435acfc5EnglishSymplectic Elements at Oxford2011Balogh, JBollobás, BMorris, RRiordan, OIn $\HH$-bootstrap percolation, a set $A \subset V(\HH)$ of initially 'infected' vertices spreads by infecting vertices which are the only uninfected vertex in an edge of the hypergraph $\HH$. A particular case of this is the $H$-bootstrap process, in which $\HH$ encodes copies of $H$ in a graph $G$. We find the minimum size of a set $A$ that leads to complete infection when $G$ and $H$ are powers of complete graphs and $\HH$ encodes induced copies of $H$ in $G$. The proof uses linear algebra, a technique that is new in bootstrap percolation, although standard in the study of weakly saturated graphs, which are equivalent to (edge) $H$-bootstrap percolation on a complete graph. |
| spellingShingle | Balogh, J Bollobás, B Morris, R Riordan, O Linear algebra and bootstrap percolation |
| title | Linear algebra and bootstrap percolation |
| title_full | Linear algebra and bootstrap percolation |
| title_fullStr | Linear algebra and bootstrap percolation |
| title_full_unstemmed | Linear algebra and bootstrap percolation |
| title_short | Linear algebra and bootstrap percolation |
| title_sort | linear algebra and bootstrap percolation |
| work_keys_str_mv | AT baloghj linearalgebraandbootstrappercolation AT bollobasb linearalgebraandbootstrappercolation AT morrisr linearalgebraandbootstrappercolation AT riordano linearalgebraandbootstrappercolation |