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.

Mixing for two nearby nested sets — Lemma 3.7

PDF p. 20: Lemma 3.7 and proof; PDF p. 21: Lemma 3.7 and proof

Statement

Let $G = (V, E)$ be an $(n, d^{*}, α, c^{-}, c^{+})$ -expander, with $c^{+} \neq c^{-}$ , and let $ε > 0$ . Thus $n = ∣ V ∣ > 0$ , and the centered Laplacian $Δ_{L} = L - d^{*} I + (d^{*} / n) J$ obeys $c^{-} d^{*} I ⪯ Δ_{L} ⪯ c^{+} d^{*} I$ in quadratic-form order. For $P, Q \subseteq V$ , let $e (P, Q)$ be the ordered adjacency count and $P^{c} = V ∖ P$ . Put $δ = ε / (c^{+} - c^{-})$ . If $X \subseteq Y \subseteq V$ , $∣ Y ∣ \leq n / 2$ , and $(1 + δ) ∣ X ∣ \geq ∣ Y ∣$ , then

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

Statement references

Two-sided spectral expander — Definition 1.9

Oriented edge count between sets

Facts & Assumptions

[F1]

In the expander definition, $n > 0$ and $c^{-} d^{*} I ⪯ Δ_{L} ⪯ c^{+} d^{*} I$ , where matrix order means nonnegativity of the corresponding quadratic forms (Two-sided spectral expander — Definition 1.9).

[F2]

For every $Z \subseteq V$ , writing $q (Z) = ∣ Z ∣ ∣ Z^{c} ∣$ , the cut bound is $c^{-} (d^{*} / n) q (Z) \leq e (Z, Z^{c}) - (d^{*} / n) q (Z) \leq c^{+} (d^{*} / n) q (Z)$ (Cut-edge mixing bound — Lemma 3.4).

[F3]

For nested sets $X \subseteq Y$ , $2 e (X, Y^{c}) = e (X, X^{c}) + e (Y, Y^{c}) - e (Y ∖ X, (Y ∖ X)^{c})$ (Nested-cut polarization identity). The edge count is the finite ordered adjacency sum, and complements are relative to $V$ (Oriented edge count between sets).

Proof

Given: An expander, parameters and nested sets satisfying the statement.

Goal: Prove the two bounds for $e (X, Y^{c})$ .

1.1F3algebra

Put $B = Y ∖ X$ , $a = ∣ X ∣$ , $b = ∣ B ∣$ , and $c = ∣ Y^{c} ∣$ . The three sets $X, B, Y^{c}$ partition $V$ , so $n = a + b + c$ , $∣ Y ∣ = a + b$ , and $b \leq δ a$ . Also $c \geq n / 2$ and $a \leq c$ . Consequently $q (X) = a (b + c)$ , $q (Y) = (a + b) c$ , $q (B) = b (a + c)$ , and $q (X) + q (Y) - q (B) = 2 a c$ . By [F3], $e (X, Y^{c}) - (d^{*} / n) a c$ is half the sum of the centered cut counts for $X$ and $Y$ minus that for $B$ .

2.1F1F2F3step 1.1algebra

Since $V$ is nonempty, testing the difference of the two order bounds in [F1] on a nonzero coordinate vector gives $(c^{+} - c^{-}) d^{*} \geq 0$ . If $d^{*} < 0$ , then $c^{+} - c^{-} < 0$ , hence $δ < 0$ . The inequalities $0 \leq b \leq δ a$ force $a = b = 0$ , and the desired bounds are both $0 \leq 0$ by the ordered-count definition. If $d^{*} = 0$ , [F2] makes all three cuts in [F3] zero, so $e (X, Y^{c}) = 0$ and both bounds again hold.

3.1F2step 1.1step 2.1algebra

It remains to consider $d^{*} > 0$ . Step 2.1 and $c^{+} \neq c^{-}$ give $w : = c^{+} - c^{-} > 0$ , so $δ = ε / w > 0$ . Apply the lower and upper bounds in [F2] to the three centered cut counts in step 1.1, reversing the choice of bound for the subtracted cut. This yields $c^{-} (d^{*} / n) a c - (d^{*} / 2 n) w b (a + c) \leq e (X, Y^{c}) - (d^{*} / n) a c \leq c^{+} (d^{*} / n) a c + (d^{*} / 2 n) w b (a + c)$ .

4.1step 1.1step 2.1step 3.1algebra∎

Because $b \leq δ a$ and $a \leq c$ , we have $w b (a + c) / 2 \leq w δ a c = ε a c$ . Multiplying by $d^{*} / n > 0$ and substituting into step 3.1 proves the asserted bounds. Together with step 2.1, this covers every defined case.

Source notes

The statement and cut-polarization method are attributed to Lemma 3.7 of Expander graphs are globally synchronizing. The proof uses the local suppliers and explicitly handles the real-parameter cases allowed by their definition; the article is not used as a proof premise.

Depends on

Used by · 2

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 · PDF pp. 20–21, Lemma 3.7 and its proof