Saturation in the hypercube and bootstrap percolation

Journal article

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 Pkd which is weakly saturated with respect to ‘axis aligned’ copies of a smaller grid Prm . We also study weak saturation of cycles in the grid.

Authors: Morrison, N; Noel, J; Scott, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Cambridge University Press
• Journal: Combinatorics Probability and Computing
• Volume: 26
• Issue: 1
• Pages: 78-98
• Publication date: 2016-03-31
• Acceptance date: 2015-06-01
• DOI: 10.1017/S0963548316000122
• EISSN: 1469-2163
• ISSN: 0963-5483
• Keywords: SBTMR