Name
Abstract | ||
|---|---|---|
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 \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}G \subset E(K_n)\end{align*} \end{document} **image** of initially ‘infected’ edges, we infect, at each time step, a new edge e if there is a copy of H in \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}K_n\end{align*} \end{document} **image** 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 \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}K_n\end{align*} \end{document} **image** is infected. The extremal questions for this model, when H is the complete graph \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}K_r\end{align*} \end{document} **image** , 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 \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}p_c(n,K_r)\end{align*} \end{document} **image** for the \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}K_r\end{align*} \end{document} **image** -process up to a poly-logarithmic factor. In the case \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}r = 4\end{align*} \end{document} **image** we prove a stronger result, and determine the threshold for \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}p_c(n,K_4)\end{align*} \end{document} **image** . © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 (Supported by CNPq bolsa de Produtividade em Pesquisa.) |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1002/rsa.20458 | Random Struct. Algorithms |
Keywords | Field | DocType |
complete graph,h-bootstrap process,wiley periodicals,graph bootstrap percolation,not-yet infected edge,g percolate,graph h,inc. random struct,critical probability,new edge e,cellular automaton,graph theory | Graph theory,Complete graph,Discrete mathematics,Graph,Combinatorics,Bootstrap percolation,Mathematics | Journal |
Volume | Issue | ISSN |
41 | 4 | 1042-9832 |
Citations | PageRank | References |
3 | 0.52 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| József Balogh | 1 | 862 | 89.91 |
| Béla Bollobás | 2 | 2696 | 474.16 |
| Robert Morris | 3 | 101 | 13.12 |