Spectral quantities for the COBRA cover time (EPI-4) #
Cooper, Radzik, Rivera, The coalescing-branching random walk on expanders and the dual epidemic process, PODC 2016 (arXiv:1602.05768), Section 1 and the proof of Lemma 1 (Section 3).
For a connected r-regular graph G the random walk has transition matrix P = A(G) / r, with
eigenvalues 1 = λ₁ ≥ λ₂ ≥ ⋯ ≥ λₙ ≥ -1, and the paper's λ = λ_max = max_{i ≥ 2} |λᵢ|. Since
λₙ ≤ λ₂, this is max {λ₂, |λₙ|}: the core's Dynamics.lambdaG, built on
Dynamics.transitionMatrix and Dynamics.walkEigenvalues (Dynamics/Spectral.lean, shared with
the median package).
The spectral core of Lemma 1 is ‖P 1_A‖² ≤ λ² |A| + (1 - λ²) |A|² / n, where
(P 1_A)(x) = d_A(x) / r and d_A(x) = |N(x) ∩ A| (sum_sq_neighbor_le).
A positive-degree regular simple graph has at least two vertices.
Double counting: ∑_x d_A(x) = r |A| on an r-regular graph.
(P 1_A)(x) = d_A(x) / r.
‖P 1_A‖² = ∑_x (d_A(x) / r)².
If λ < 1, expand 1_A in the eigenbasis of P: the top eigenvalue is 1 with squared
coefficient |A|² / n, and every other eigenvalue has square at most λ².
Spectral core of Lemma 1 (Section 3, inequality (7)): on an r-regular graph with
r > 0, for every set A,
∑ₓ P(x, A)² = ‖P 1_A‖² ≤ λ² |A| + (1 - λ²) |A|² / n, where P(x, A) = d_A(x) / r.
Proof idea: expand 1_A in an orthonormal eigenbasis of P; the top eigenvector is the constant
vector 1/√n (coefficient |A| / √n) and every other eigenvalue has square ≤ λ². If λ ≥ 1
the bound follows from P(x, A) ≤ 1 and ∑ₓ P(x, A) = |A|.