Answers are grounded in this paper and cite their sources.
Graph bootstrap percolation is a deterministic cellular automaton which was introduced by Bollobás in 1968, and is defined as follows. Given a graph H , and a set {article}{mathrsfs}{amsmath, amssymb}{empty}{document}{align*}G ⊂ E(K_n){align*} {document} of initially ‘infected’ edges, we infect, at each time step, a new edge e if there is a copy of H in {article}{mathrsfs}{amsmath, amssymb}{empty}{document}{align*}K_n{align*} {document} 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 {article}{mathrsfs}{amsmath, amssymb}{empty}{document}{align*}K_n{align*} {document} is infected. The extremal questions for this model, when H is the complete graph {article}{mathrsfs}{amsmath, amssymb}{empty}{document}{align*}K_r{align*} {document} , 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 {article}{mathrsfs}{amsmath, amssymb}{empty}{document}{align*}p_c(n,K_r){align*} {document} for the {article}{mathrsfs}{amsmath, amssymb}{empty}{document}{align*}K_r{align*} {document} ‐process up to a poly‐logarithmic factor. In the case {article}{mathrsfs}{amsmath, amssymb}{empty}{document}{align*}r = 4{align*} {document} we prove a stronger result, and determine the threshold for {article}{mathrsfs}{amsmath, amssymb}{empty}{document}{align*}p_c(n,K_4){align*} {document} .
No takes yet. Share an insight, caveat, or question.
Balogh et al. (2012) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: