Documentation

Epidemics.CobraCoverSpectral

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).

theorem Epidemics.two_le_card_of_pos_regular {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {r : ℕ} (hreg : G.IsRegularOfDegree r) (hr : 0 < r) [Nonempty V] :

A positive-degree regular simple graph has at least two vertices.

theorem Epidemics.sum_neighborCard_eq {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {r : ℕ} (hreg : G.IsRegularOfDegree r) (A : Finset V) :
∑ x : V, (G.neighborFinset x ∩ A).card = r * A.card

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 λ².

theorem Epidemics.sum_sq_neighbor_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {r : ℕ} (hreg : G.IsRegularOfDegree r) (hr : 0 < r) (A : Finset V) :
∑ x : V, (↑(G.neighborFinset x ∩ A).card / ↑r) ^ 2 ≤ Dynamics.lambdaG G r ^ 2 * ↑A.card + (1 - Dynamics.lambdaG G r ^ 2) * ↑A.card ^ 2 / ↑(Fintype.card V)

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|.