The infimum over \(I_0\) is attained; take the second-to-last vertex of a shortest walk; a shortest walk is a path.

Both statements together, by induction on \(t\), using Lemma 2.

Immediate from Theorem 3 and \(d(v){\lt}|V|\) when finite.

The two events coincide for every coin assignment (Corollary 4).

Markov’s inequality on \(e^{\varepsilon X}\) and the bound \(\mathbb E[e^{\varepsilon X}] \le \exp (\mu (e^{\varepsilon }-1))\) for a sum of independent trials with mean \(\mu \le (1-\varepsilon )(t+1)\) (the Chernoff layer of the shared dynamics package, before optimizing the tilt: Distribution.prob_ge_le_exp), then \((1-\varepsilon )e^{\varepsilon } \le 1 - \varepsilon ^2/2\).

For an exploration state (discovered set \(D\), examined pairs \(X\), forced closed), induction on a budget \(m \ge \mathrm{frontier}(D, X) + (k-1)(d-1)\): conditioning on the coin of one frontier edge, a closed coin removes that edge from the frontier, and an open one adds a vertex and at most \(d-1\) new frontier edges at it while removing the examined one. This is the recursion of the binomial tail. The initial frontier of \(\{ s\} \) has at most \(d\) edges.

Theorem 7 and Lemma 6, then a union bound over the vertices.

The final outbreak is the union of the components of \(I_0\), and distances inside a component are smaller than its size (Corollary 4). \(G(n, c/n)\) is bond percolation on \(K_n\), with \(d = n - 1\) and \(p(d-1) \le c\).

A pair is an open edge if and only if its percolation coin is open and it is a cycle edge or an open bridge; these combined coins are independent across pairs, with the stated probabilities.

Condition on the history: the event that the history is \(h\) depends only on the coordinates read along \(h\), which are independent of the fresh ones (principle of deferred decisions); induction on the number of steps.

The exponential of \(\theta \) times (discovered weight \(-\ \kappa \lambda \, \cdot \) processed weight) is a supermartingale, by \(1 - r + r e^x \le e^{\kappa r x}\) for \(0 \le x \le \kappa - 1 \le 1\) and Lemma 12. A cluster with more than \(t\) nodes leaves \(t\) processed and \(t + 1\) discovered nodes after \(t\) steps; Markov’s inequality concludes.

Weights \(1\) (discovered through a cycle edge: at most one undiscovered cycle neighbour) and \(1 + p_0\) (otherwise: at most two), and at most \(n\) further pairs each open with probability \(pc/n\): the expected discovered weight is at most \((1 - \delta /2)\) times the weight. Apply Theorem 13 with \(\theta = \delta /8\), \(\kappa = 1 + \delta /4\) and a union bound over the nodes.

Theorem 8 with \(d = 3\) and \(2\varepsilon \) in place of \(\varepsilon \).

Deterministic consequences of the component bounds (Corollary 9).

The answers equal a list \(L\) iff the coordinates queried along \(L\), which are determined by \(L\) and distinct, take the values of \(L\): a cylinder event of probability \(\prod _k w(L_k)\).

An invariant preserved by every move and answer; moves without query terminate because \(2|S|+|U|\le 2n\) increases.

In each case \(|S||T|\) (or \(|D|(n-|D|)\)) would exceed the number of queries.

Chernoff bounds and the union bound.

Run the search for \(N_0=\lfloor \varepsilon n^2/2\rfloor \) queries; on the typical event the stack is a path of the required length.

No epoch starts between the times \(t_1=\lfloor \eta n^2\rfloor \) and \(N_0=\lfloor \theta n^2\rfloor \), so the positive answers in between lie in one component; \(\theta =\varepsilon /2\) for the first statement, \(\theta \) small in terms of \(\varepsilon \) for the second.

The final outbreak is the component of the initial node (Corollary 4); by symmetry of \(K_n\) this node lies in a component of size \(\ge k\) with probability at least \(k/n\) times the probability that such a component exists.

The derivatives of \(s+i+r\) and of \(se^{R_0r}\) vanish (\(R_0\gamma =\beta \)), and a function with zero right derivative is constant. For \(i{\gt}0\), compare \(i\) with the barrier \(b(t)=\tfrac {i(0)}2e^{-\gamma t}\): where they touch, \(b'=-\gamma i{\lt}\beta si-\gamma i=i'\) since \(s{\gt}0\), so \(i\ge b\). Monotonicity follows from the signs of \(s'=-\beta si\) and \(r'=\gamma i\).

\(i'=i(\beta s-\gamma )\) and \(s(t){\lt}s(0)\) for \(t{\gt}0\). If \(R_0s(0){\gt}1\), then \(\beta s-\gamma {\gt}0\) near \(0\) by continuity.

\(s\) and \(r\) are monotone and bounded, so \(i=1-s-r\) converges; if \(i\to L{\gt}0\), the mean value theorem makes \(r\) grow by more than \(1\). Pass to the limit in \(s=s(0)e^{-R_0r}\). If \(R_0s_\infty \ge 1\) then \(i'{\gt}0\) forever, contradicting \(i\to 0\). Uniqueness: \(\log x-R_0x\) is strictly increasing on \((0,1/R_0]\) and strictly decreasing on \([1/R_0,\infty )\), and at \(x=1\) it exceeds its value \(\log s(0)-R_0\) at the roots because \(s(0){\lt}1\).

Intermediate value theorem between \(s(0){\gt}1/R_0\) and \(s_\infty {\lt}1/R_0\); the sign of \(\beta s-\gamma \) changes at \(t_{\max }\). The value follows from \(\log s=\log s(0)-R_0r\) and \(r=1-s-i\).

Among the \(N^2(\beta +\gamma )\) rounds, \(\beta IS\) move an agent from \(S\) to \(I\) and \(\gamma NI\) move one from \(I\) to \(R\); a round changes the compartment of at most one agent.

Hoeffding’s lemma (\(\mathbb E e^{\theta D}\le \cosh (\theta c)\le e^{\theta ^2c^2/2}\) by convexity) makes \(e^{\theta M_k-k\theta ^2c^2/2}\) a nonnegative supermartingale; Ville’s maximal inequality, proved by induction on \(n\) peeling off the first round, bounds the probability that it reaches \(\mu \) by \(1/\mu \); take \(\theta =\lambda /(nc^2)\).

The simplex is invariant under the ODE (first integral for \(s\), integrating factor for \(i\)); there \(F\) is \((2\beta +\gamma )\)-Lipschitz and bounded by \(\beta +\gamma \), so one Euler step errs by \(O(h^2)\), \(h=1/((\beta +\gamma )N)\). By Lemma 31 each coordinate of \(X_k-X_0-h\sum _{j{\lt}k}F(X_j)\) is a martingale with increments at most \(2/N\); on the event where the six one-sided maximal deviations stay below \(\delta =\varepsilon /(2L)\), the discrete Grönwall inequality gives the bound with \(L=e^{(2\beta +\gamma )T}\), once \(\varepsilon N\ge 2LT(2\beta +\gamma )\); Lemma 32 bounds the complement by \(6e^{-c\varepsilon ^2N}\). Small \(N\) and \(\varepsilon \ge 2\) are absorbed in \(C\).

Expand the variance of a sum of indicators.

The potential \(n-|S|\) (set to \(0\) once \(|S|\ge m\)) contracts by \(1-p\) in expectation.

Phases \(k_{j+1}=k_j+E_0(k_j)\) with a round target \(E_0(k)=E(k)-Ak^{3/4}\); Cantelli’s inequality (Lemma 36) bounds the probability of missing a target, and a phase potential on the iterated kernel replaces the paper’s domination by geometric variables. Lemma 37 crosses the last stretch up to \(fn\).

Chebyshev’s inequality with Lemma 36 for one round, then a union bound over the rounds along the trajectory.

Lemma 37 first brings the number \(u\) of uninformed nodes below \(g_0n\); then the potential \(\Phi =u+\frac\beta nu^2\) satisfies \(E[\Phi ']\le e^{-\rho }(1+K/n)\Phi \) (Lemma 36 for the second moment), which replaces the paper’s phase calculus.

Compose the three exponential tails (Theorem 38, Lemma 37, Theorem 40) by the Markov property at fixed times, and sum the tail.

Three stages. Geometric targets \(g\mu ^jn\), \(\mu =(1+ag^{\ell -1})/2\), bring \(u\) below \(g_0n\) in a constant number of phases; double exponential targets \(\varepsilon _{j+1}=2a_1\varepsilon _j^\ell \), i.e. \(\varepsilon _j=e^{-(\kappa +\ell ^jD_0)}\), bring it below \(\varepsilon _Jn\le n^{1-\beta /(2\ell )}\) in \(J\le \log _\ell \ln n\) phases; below that, every uninformed node stays uninformed with probability at most \(n^{-\tau _3}\) and Markov’s inequality finishes. A phase fails with probability at most \(n^{-2\delta }\) (Chebyshev with Lemma 36 above \(n^{1-\alpha }\) uninformed nodes, Markov with fast finishing below), and the phase potential \(\lambda ^{J-j}\), \(\lambda =n^\delta \), contracts by \(n^{-2\delta }+n^{-\delta }\) per round. The paper’s first stage uses Lemma 19, whose tail rate does not depend on \(n\); the per-round Chebyshev bound gives the polynomial tail.

As Theorem 41, with Theorem 43 in the last stage (its polynomial tail is an exponential tail once \(\ln n\ge 1\)).

The calls are independent uniform coordinates, so the events “\(x\) stays uninformed” and “\(x\) and \(y\) stay uninformed” have product probabilities. The bounds use \((1-x)^k\le 1-kx+(kx)^2/2\) and \(e^t\le 1+2t\) on \([0,1]\).

Instantiate Theorem 41 (push) and Theorem 44 (pull, push–pull) with Lemma 46; the middle range is empty since \(f=g=\frac12\).

Every vertex of a connected graph with at least two vertices has a neighbour.

The uniform average over \(\mathrm{Fin}\, T\to \alpha \) is invariant under \(\omega \mapsto \omega \circ \mathrm{rev}\) (the time-reversal lemma of the shared dynamics package).

Induction on \(t\), generalizing \(C\). Both sides say that a chain \(x_0\in C\), \(x_j=r_j(x_{j-1},i_j)\), reaches \(v\) within \(t\) steps: COBRA unfolds the first round, BIPS the last round of the reversed sequence.

Lemma 51 identifies the two events after reversing the rounds, and Lemma 50 says that reversing the rounds preserves their law. The paper proves the theorem instead by induction on \(t\) with one-step conditioning.