Graph bootstrap percolation

Details Graph bootstrap percolation Graph bootstrap percolation

2011-07-07

arxiv.org/abs/1107.1381v1

Mathematics

Combinatorics

25 pages

Scientific paper

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 \subset 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)$.

Affiliated with

Also associated with

No associations

Rating

Graph bootstrap percolation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph bootstrap percolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph bootstrap percolation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-416976