The Library
Saturation in the hypercube and bootstrap percolation
Tools
Tools
Tools
Morrison, Natasha, Noel, Jonathan A. and Scott, Alex (2017) Saturation in the hypercube and bootstrap percolation. Combinatorics, Probability and Computing, 26 (1). pp. 78-98. doi:10.1017/S0963548316000122 ISSN 0963-5483.
|
PDF
WRAP-saturation-hypercube-bootstrap-percolation-Noel-2017.pdf - Accepted Version - Requires a PDF viewer. Download (707Kb) | Preview |
Official URL: http://dx.doi.org/10.1017/S0963548316000122
Abstract
Let Qd denote the hypercube of dimension d. Given d ⩾ m, a spanning subgraph G of Qd is said to be (Qd , Qm)-saturated if it does not contain Qm as a subgraph but adding any edge of E (Qd) \ E (G) creates a copy of Qm in G. Answering a question of Johnson and Pinto [27], we show that for every fixed m ⩾ 2 the minimum number of edges in a (Qd, Qm)-saturated graph is Θ(2 d).
We also study weak saturation, which is a form of bootstrap percolation. A spanning subgraph of Qd is said to be weakly (Qd , Qm )-saturated if the edges of E (Qd ) \ E (G) can be added to G one at a time so that each added edge creates a new copy of Qm . Answering another question of Johnson and Pinto [27], we determine the minimum number of edges in a weakly (Qd , Qm )-saturated graph for all d ⩾ m ⩾ 1. More generally, we determine the minimum number of edges in a subgraph of the d-dimensional grid Pk d which is weakly saturated with respect to ‘axis aligned’ copies of a smaller grid Pr m . We also study weak saturation of cycles in the grid.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
| Library of Congress Subject Headings (LCSH): | Bootstrap (Statistics), Hypercube | ||||||||
| Journal or Publication Title: | Combinatorics, Probability and Computing | ||||||||
| Publisher: | Cambridge University Press | ||||||||
| ISSN: | 0963-5483 | ||||||||
| Official Date: | January 2017 | ||||||||
| Dates: |
|
||||||||
| Volume: | 26 | ||||||||
| Number: | 1 | ||||||||
| Page Range: | pp. 78-98 | ||||||||
| DOI: | 10.1017/S0963548316000122 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 10 July 2018 | ||||||||
| Date of first compliant Open Access: | 11 July 2018 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
