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-edge mixing bound — Lemma 3.4

PDF p. 19: Lemma 3.4; PDF p. 20: Lemma 3.4

Statement

Let $G = (V, E)$ be an $(n, d^{*}, α, c^{-}, c^{+})$ -expander as in Two-sided spectral expander — Definition 1.9, and let $X \subseteq V$ . Write $X^{c} = V ∖ X$ and let $e (X, X^{c})$ be the ordered edge count of Oriented edge count between sets. Then

$c^{-} \frac{d^{*}}{n} ∣ X ∣ ∣ X^{c} ∣ \leq e (X, X^{c}) - \frac{d^{*}}{n} ∣ X ∣ ∣ X^{c} ∣ \leq c^{+} \frac{d^{*}}{n} ∣ X ∣ ∣ X^{c} ∣ .$

Facts & Assumptions

[F1]

The expander definition has $n = ∣ V ∣ > 0$ , $Δ_{L} = L - d^{*} I + (d^{*} / n) J$ , and $c^{-} d^{*} I ⪯ Δ_{L} ⪯ c^{+} d^{*} I$ . Here $L$ is the row-sum Laplacian, $I$ is the identity, and $J$ is the all-ones matrix (Two-sided spectral expander — Definition 1.9).

[F2]

For Hermitian matrices, $B ⪯ C$ means that $⟨ f, (C - B) f ⟩ \geq 0$ for every complex vector $f$ , with $⟨ f, g ⟩ = \sum_{x \in V} \overline{f (x)} g (x)$ (Loewner order, Hermitian inner product, and operator norm).

[F3]

If $1_{X}$ and $1_{X^{c}}$ are the indicators of $X$ and $X^{c}$ and $f = ∣ X^{c} ∣ 1_{X} - ∣ X ∣ 1_{X^{c}}$ , then $⟨ f, f ⟩ = n ∣ X ∣ ∣ X^{c} ∣$ and $⟨ f, Δ_{L} f ⟩ = n^{2} (e (X, X^{c}) - (d^{*} / n) ∣ X ∣ ∣ X^{c} ∣)$ (Cut test-vector identities for Laplacian mixing).

Proof

Given: An expander $G$ and a subset $X \subseteq V$ as in the statement.

Goal: Establish both displayed bounds on the centered cut count.

1.1F1F2F3

Take the cut vector $f$ of [F3]. Applying the two order inequalities in [F1] to this vector using [F2] yields $c^{-} d^{*} ⟨ f, f ⟩ \leq ⟨ f, Δ_{L} f ⟩ \leq c^{+} d^{*} ⟨ f, f ⟩$ . This application is valid also when $f = 0$ .

2.1F1F3step 1.1algebra∎

Substitute the two identities in [F3] into step 1.1 and divide throughout by $n^{2} > 0$ , using $n > 0$ from [F1]. The result is precisely the asserted pair of inequalities. This includes $X = \emptyset$ and $X = V$ .

Source notes

The statement and the cut-vector method are attributed to Lemma 3.4 of Expander graphs are globally synchronizing. The argument above derives the claim from the stated local suppliers.

Depends on

Used by · 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 pp. 19–20, Lemma 3.4 and its proof