BOOTSTRAP PERCOLATION, CONNECTIVITY, AND GRAPH DISTANCE

NEW

Problem: Reconstructed statement: Let $G$ be a finite simple connected graph. In $r$-bootstrap percolation, an initial infected set is $S_1=A_0$, and for $i\ge2$, $S_i$ is the set of vertices newly infected in round $i$. If $A_0$ percolates in exactly $k$ rounds at threshold $r\ge2$, and $\operatorname{diam}_D(G)$ denotes the length of a longest simple path in $G$, then the conjecture asserts

$$k\le \operatorname{diam}_D(G).$$

This matches the paper’s convention that the initial round is round $1$.

Literal defect: if $G=K_1$, $A_0=V(G)$, and $r\ge2$, then $k=1$ but $\operatorname{diam}_D(G)=0$. Thus the literal statement is false for the one-vertex graph. The natural repair is to assume $|V(G)|\ge2$. Under that minimal repair, the conjecture is true.

Result: The repaired conjecture is true.

Proof. Let $S_i$ be the vertices newly infected in round $i$, so $S_1=A_0$, $S_k\neq\varnothing$, and $S_i\cap S_j=\varnothing$ for $i\neq j$.

If $k=1$, then $A_0=V(G)$. Since $|V(G)|\ge2$ and $G$ is connected, $G$ has an edge, so $\operatorname{diam}_D(G)\ge1=k$.

Assume $k\ge2$. Choose $x_k\in S_k$. For each $i=k,k-1,\dots,2$, choose $x_{i-1}\in S_{i-1}$ adjacent to $x_i$. This is possible because if $x_i$ had no neighbor in $S_{i-1}$, then all its infected neighbors before round $i$ were already infected before round $i-1$, so $x_i$ would have been infected earlier.

Thus

$$x_1x_2\cdots x_k$$

is a simple path with $x_i\in S_i$. Since $r\ge2$, each $x_i$, $i\ge2$, has at least two neighbors in $S_1\cup\cdots\cup S_{i-1}$. Besides $x_{i-1}$, choose another such neighbor $y_i$.

We now show these extra neighbors force a path of length $k$. Start with the path

$$P=(y_2,x_2,x_3,\dots,x_k),$$

which has $k$ vertices and length $k-1$. It excludes $x_1$, and $x_1x_2\in E(G)$.

Maintain a path whose vertex set is $\{y_2,x_2,\dots,x_k\}$, whose first vertex is $y_2$, and whose last vertex is some $x_e$, with initial segment

$$y_2,x_2,\dots,x_{e-1}.$$

Initially $e=k$. If $y_e\notin V(P)$, append $y_e$ to get a path of length $k$. If $y_e=y_2$, then $P$ plus edge $x_ey_2$ is a cycle through $y_2,x_2,\dots,x_k$; attaching $x_1$ at $x_2$ gives a path of length $k$.

Otherwise $y_e=x_j$ for some $2\le j\le e-2$, because $y_e$ was infected before round $e$ and $y_e\neq x_{e-1}$. Rotate the path at $x_j$: replace

$$y_2,x_2,\dots,x_j,x_{j+1},\dots,x_e$$

by

$$y_2,x_2,\dots,x_j,x_e,\dots,x_{j+1}.$$

This keeps the same vertex set and changes the last vertex to $x_{j+1}$, whose index is smaller than $e$. The maintained initial-segment property remains true. Repeating, the endpoint index strictly decreases, so the process terminates, and termination yields a path of length $k$.

Therefore $G$ contains a simple path of length at least $k$. Hence

$$\operatorname{diam}_D(G)\ge k.$$

So $k\le\operatorname{diam}_D(G)$.

Citation: The conjecture and definitions are from Lafayette–Ibrahim–McCall, “Bootstrap Percolation, Connectivity, and Graph Distance,” arXiv:2309.13138. I am not aware of a prior published resolution; the proof above resolves the repaired nontrivial statement.