§3.1, Eq. (3.1) — bilinear cut identity over F₂: Σ_{u∈C}(h_u y_uᵀ + y_u h_uᵀ) = H X_C Hᵀ
ProvedSpanForestStream.Unrestricted.eq_3_1graph-theoryp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1streaming-algorithms
Let be a simple graph on with symmetric adjacency matrix over , a vertex set with diagonal indicator , an matrix over , its column , and the retained syndrome of vertex . Let be the crossing-edge adjacency matrix, with entry exactly at the pairs that are edges of with exactly one endpoint in . Then over , and
The identity lets the algorithm assemble the syndrome of a cut from the stored vertex syndromes.
Differences from the source:
- generalization: H is the binary syndrome matrix of the sparse-recovery code of Lemma 3.1 → H is any s × v matrix over F₂; reason: the identity uses no property of H, and the syndrome matrix is an instance
- encoding: y_u = H x_u with x_u the adjacency column of u, and the identity y_u = HXe_u → y_u defined as (HX)e_u; reason: x_u = Xe_u, so the two definitions agree
- encoding: the crossing-edge adjacency matrix X_C → the 0/1 matrix with entry 1 iff G.Adj a b and exactly one of a, b lies in C; reason: the explicit meaning of 'crossing edge'
Preamble
import Mathlib
Formal statement
namespace SpanForestStream.Unrestricted
/-- §3.1, Eq. (3.1): over `F₂`, with `X` the symmetric adjacency matrix of a simple graph `G` on
`[v]`, `I_C` the diagonal indicator of `C`, `h_u = H e_u` and `y_u = H X e_u`, the crossing-edge
adjacency matrix is `X_C = I_C X + X I_C`, and
`Σ_{u ∈ C} (h_u y_uᵀ + y_u h_uᵀ) = H (I_C X + X I_C) Hᵀ = H X_C Hᵀ`. -/
theorem eq_3_1 {v s : ℕ} (G : SimpleGraph (Fin v)) [DecidableRel G.Adj]
(H : Matrix (Fin s) (Fin v) (ZMod 2)) (C : Finset (Fin v)) :
let X : Matrix (Fin v) (Fin v) (ZMod 2) := G.adjMatrix (ZMod 2)
let IC : Matrix (Fin v) (Fin v) (ZMod 2) := Matrix.diagonal fun u => if u ∈ C then 1 else 0
let XC : Matrix (Fin v) (Fin v) (ZMod 2) :=
fun a b => if G.Adj a b ∧ (a ∈ C ↔ b ∉ C) then 1 else 0
let h : Fin v → Fin s → ZMod 2 := fun u => H.mulVec (Pi.single u 1)
let y : Fin v → Fin s → ZMod 2 := fun u => (H * X).mulVec (Pi.single u 1)
XC = IC * X + X * IC ∧
∑ u ∈ C, (Matrix.vecMulVec (h u) (y u) + Matrix.vecMulVec (y u) (h u)) =
H * (IC * X + X * IC) * H.transpose ∧
H * (IC * X + X * IC) * H.transpose = H * XC * H.transpose := by sorry
end SpanForestStream.Unrestricted
Source
Chao, Cen, Ma, Wang, Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level, arXiv:2611.04365 (PDF sha256 00f5bb17…69c92), p. 13 (PDF 16), proof of Lemma 3.1, Eq. (3.1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.