Graph bootstrap percolation

DOI10.1002/RSA.20458MaRDI QIDQ3145835zbMATH OpenOpenAlexFDO

Authors József Balogh, Béla Bollobás, Robert Morris

Publication date 14 December 2012

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.1381

bootstrap percolation graph theory weak saturation

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Cellular automata (computational aspects) (68Q80)

Abstract: Graph bootstrap percolation is a deterministic cellular automaton which was introduced by Bollob'as in 1968, and is defined as follows. Given a graph

H

, and a set

G s u b s e t E (K_{n})

of initially `infected' edges, we infect, at each time step, a new edge

e

if there is a copy of

H

in

K_{n}

such that

e

is the only not-yet infected edge of

H

. We say that

G

percolates in the

H

-bootstrap process if eventually every edge of

K_{n}

is infected. The extremal questions for this model, when

H

is the complete graph

K_{r}

, were solved (independently) by Alon, Kalai and Frankl almost thirty years ago. In this paper we study the random questions, and determine the critical probability

p_{c} (n, K_{r})

for the

K_{r}

-process up to a poly-logarithmic factor. In the case

r = 4

we prove a stronger result, and determine the threshold for

p_{c} (n, K_{4})

.

Recommendations

Cites work

Cited in

(53)

This page was built for publication: Graph bootstrap percolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3145835)