# Extremal $4$-Neighbour Bootstrap Percolation in the Hypercube

 Importance: Medium ✭✭
 Author(s): Morrison, Natasha Noel, Jonathan A.
 Subject: Combinatorics
 Keywords: bootstrap percolation extremal combinatorics hypercube percolation
 Posted by: Jon Noel on: September 20th, 2015

\begin{problem} Determine the smallest percolating set for the $4$-neighbour bootstrap process in the hypercube. \end{problem}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

The \emph{$r$-neighbour bootstrap process} starts with an initial set of "infected" vertices in a graph and, at each step, a healthy vertex becomes infected if it has at least $r$ infected neighbours. Say that the initial set of infected vertices \emph{percolates} if every vertex of $G$ is eventually infected. Let $m(G,r)$ denote the smallest percolating set in $G$ under the $r$-neighbour process.

Let $Q_d$ denote the hypercube of dimension $d$. Balogh and Bollobás [BB] proved the following.

\begin{theorem}[Balogh and Bollobás] $m(Q_d,2) = \left\lceil \frac{d}{2}\right\rceil +1$ for all $d\geq 2$. \end{theorem}

They also conjectured that $m(Q_d,r) = \frac{1+o(1)}{r}\binom{d}{r-1}$ for fixed $r$ and $d\to\infty$. This conjecture was proved by Morrison and Noel [MN], who also showed the following.

\begin{theorem}[Morrison and Noel] $m(Q_d,3) = \left\lceil \frac{d(d+3)}{6} \right\rceil +1$ for all $d\geq 3$. \end{theorem}

It seems possible that one could obtain a general formula for $m(Q_d,r)$ for all $r$ and $d\geq r$. However, the precise formula for $m(Q_d,r)$ (in terms of $d$) is not known for any fixed $r\geq4$. A solution to this problem may have applications in proving probabilistic results for bootstrap percolation in the hypercube; see [BBM].

## Bibliography

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

[BB] J. Balogh and B. Bollobás, Bootstrap percolation on the hypercube, Probab. Theory Related Fields 134 (2006), no. 4, 624–648.

[BBM] J. Balogh, B. Bollobás and R. Morris, Bootstrap percolation in high dimensions, Combin. Probab. Comput. 19 (2010), no. 5-6, 643–692.

[MN] N. Morrison and J. A. Noel, Extremal Bounds for Bootstrap Percolation in the Hypercube, preprint, arXiv:1506.04686v1.

* indicates original appearance(s) of problem.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9053211212158203, "perplexity": 2589.9469910809}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2017-47/segments/1510934807089.35/warc/CC-MAIN-20171124051000-20171124071000-00520.warc.gz"}