LemmaStatement: AI-adaptedProof: AI-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Cut test-vector identities for Laplacian mixing

PDF p. 19: Proof of Lemma 3.4

Statement

Let $G = (V, E)$ be a finite undirected graph with nonempty vertex set, at most one edge between any pair of vertices, and possible self-loops. Write $n = ∣ V ∣$ , let $A$ be its adjacency matrix, $D$ the diagonal matrix of row sums of $A$ , and $L = D - A$ . Let $I$ be the identity matrix, $J$ the all-ones matrix, and $d^{*}$ a real reference parameter. Set $Δ_{L} = L - d^{*} I + (d^{*} / n) J$ . For subsets $X, Y \subseteq V$ , put $e (X, Y) = \sum_{x \in X} \sum_{y \in Y} A_{x y}$ . The inner product is $⟨ u, v ⟩ = \sum_{x \in V} \overline{u (x)} v (x)$ .

For $X \subseteq V$ , write $X^{c} = V ∖ X$ and let $1_{X}$ be the function that is $1$ on $X$ and $0$ elsewhere. Set $f = ∣ X^{c} ∣ 1_{X} - ∣ X ∣ 1_{X^{c}}$ . Then $⟨ f, f ⟩ = n ∣ X ∣ ∣ X^{c} ∣$ , $⟨ f, L f ⟩ = n^{2} e (X, X^{c})$ , $⟨ f, J f ⟩ = 0$ , and $⟨ f, Δ_{L} f ⟩ = n^{2} (e (X, X^{c}) - (d^{*} / n) ∣ X ∣ ∣ X^{c} ∣)$ .

Facts & Assumptions

[F1]

The graph adjacency matrix is real, symmetric and nonnegative, and $e (X, Y)$ is the displayed ordered count. A loop contributes once to a row sum (Oriented edge count between sets).

[F2]

For a nonempty finite vertex set and a real symmetric nonnegative matrix, the cut-calculus proposition gives $f^{T} f = n ∣ X ∣ ∣ X^{c} ∣$ , $J f = 0$ , and $f^{T} L f = n^{2} e (X, X^{c})$ for the displayed cut vector, with $L$ formed from the row sums. It includes empty cuts and permits diagonal entries (Ordered edge counts and centered cut vectors).

[F3]

The centered Laplacian is $Δ_{L} = L - d^{*} I + (d^{*} / n) J$ (Centered graph matrices and reference degree). The displayed Hermitian inner product is linear in its second argument and agrees with transpose multiplication for real vectors (Loewner order, Hermitian inner product, and operator norm).

[F4]

For any vector $g$ , $⟨ g, J g ⟩ = ∣ \sum_{x \in V} g (x) ∣^{2}$ (The constant projection and centering decomposition).

Proof

Given: The graph, real parameter $d^{*}$ and subset $X$ in the statement.

Goal: Prove the four displayed identities.

1.1F1F2F3F4given

By [F1], the graph adjacency matrix satisfies the hypotheses of [F2], with the same row-sum Laplacian and ordered cut count. The vector $f$ is real, so [F2] and [F3] give $⟨ f, f ⟩ = n ∣ X ∣ ∣ X^{c} ∣$ and $⟨ f, L f ⟩ = n^{2} e (X, X^{c})$ . Also [F2] gives $J f = 0$ , hence $⟨ f, J f ⟩ = 0$ . Equivalently, its coordinate sum is zero and [F4] gives the same last identity.

2.1F3step 1.1givenalgebra∎

By [F3] and linearity in the second argument, $⟨ f, Δ_{L} f ⟩ = ⟨ f, L f ⟩ - d^{*} ⟨ f, f ⟩ + (d^{*} / n) ⟨ f, J f ⟩$ . Substituting step 1.1 and using $n > 0$ gives $n^{2} e (X, X^{c}) - d^{*} n ∣ X ∣ ∣ X^{c} ∣ = n^{2} (e (X, X^{c}) - (d^{*} / n) ∣ X ∣ ∣ X^{c} ∣)$ , as required.

Source notes

The cut-vector calculation is attributed to the proof of Lemma 3.4 in the cited article. The proof above is a local consequence of the stated suppliers.

Depends on

Used by · 1

Cut-edge mixing bound — Lemma 3.4

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.

Sources

Expander graphs are globally synchronizing — Abdalla, Bandeira, Kassabov, Souza, Strogatz, Townsend (2026) · PDF p. 19, proof of Lemma 3.4