Saturation in the hypercube and bootstrap percolation

Abstract: Let

Q_{d}

denote the hypercube of dimension

d

. Given

d g e q m

, a spanning subgraph

G

of

Q_{d}

is said to be

(Q_{d}, Q_{m})

-saturated if it does not contain

Q_{m}

as a subgraph but adding any edge of

E (Q_{d}) s e t m i n u s E (G)

creates a copy of

Q_{m}

in

G

. Answering a question of Johnson and Pinto, we show that for every fixed

m g e q 2

the minimum number of edges in a

(Q_{d}, Q_{m})

-saturated graph is

T h e t a (2^{d})

. We also study weak saturation, which is a form of bootstrap percolation. A spanning subgraph of

Q_{d}

is said to be weakly

(Q_{d}, Q_{m})

-saturated if the edges of

E (Q_{d}) s e t m i n u s E (G)

can be added to

G

one at a time so that each added edge creates a new copy of

Q_{m}

. Answering another question of Johnson and Pinto, we determine the minimum number of edges in a weakly

(Q_{d}, Q_{m})

-saturated graph for all

d g e q m g e q 1

. More generally, we determine the minimum number of edges in a subgraph of the

d

-dimensional grid

P_{k}^{d}

which is weakly saturated with respect to `axis aligned' copies of a smaller grid

P_{r}^{m}

. We also study weak saturation of cycles in the grid.

Recommendations

Cites Work

Cited In (13)

This page was built for publication: Saturation in the hypercube and bootstrap percolation