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.

Relative mixing for a small nested set — Lemma 3.8

PDF p. 21: Lemma 3.8 and proof

Statement

Let $G = (V, E)$ be an $(n, d^{*}, α, c^{-}, c^{+})$ -expander, with $α \neq 0$ and $c^{+} \neq c^{-}$ , and let $ε, ρ > 0$ . Thus $n = ∣ V ∣ > 0$ ; the expander condition includes the centered adjacency bound $∥ A - (d^{*} / n) J ∥ \leq α d^{*}$ and the two-sided centered Laplacian bounds. For subsets $P, Q \subseteq V$ , let $e (P, Q) = \sum_{p \in P} \sum_{q \in Q} A_{p q}$ , and let $P^{c} = V ∖ P$ . Put $δ = ε / (c^{+} - c^{-})$ . If $X \subseteq Y \subseteq V$ , $∣ Y ∣ \leq n / 2$ , $(1 + δ) ∣ X ∣ \geq ∣ Y ∣$ , and $∣ X ∣ \leq ρ α n$ , then

$e (X, Y^{c}) \geq \frac{1 + c^{-} - ε}{2 (1 + ρ) α} e (X, X) .$

The count is ordered: an internal non-loop edge contributes twice to $e (X, X)$ and an internal loop contributes once.

Facts & Assumptions

[F1]

The expander definition supplies $n > 0$ , the centered adjacency norm bound, and the centered Laplacian bounds; it imposes no separate sign restriction on the parameters (Two-sided spectral expander — Definition 1.9).

[F2]

The ordered adjacency count is a sum of nonnegative entries, and complements are relative to $V$ (Oriented edge count between sets).

[F3]

For every $X \subseteq V$ , internal-edge mixing gives $e (X, X) \leq (d^{*} / n) ∣ X ∣^{2} + α d^{*} ∣ X ∣$ (Internal-edge mixing bound — Lemma 3.3).

[F4]

Under the stated nested-set hypotheses, the lower nearby-set mixing bound is $e (X, Y^{c}) \geq (1 + c^{-} - ε) (d^{*} / n) ∣ X ∣ ∣ Y^{c} ∣$ (Mixing for two nearby nested sets — Lemma 3.7).

Proof

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

Goal: Prove the displayed relative mixing bound.

1.1givenF1F2

Since $∣ X ∣ \geq 0$ and $∣ X ∣ \leq ρ α n$ , while $ρ, n > 0$ and $α \neq 0$ , necessarily $α > 0$ . The left side of the norm bound in [F1] is nonnegative, so $d^{*} \geq 0$ . The hypothesis $∣ Y ∣ \leq n / 2$ gives $∣ Y^{c} ∣ \geq n / 2$ .

2.1F2step 1.1

Write $b = 1 + c^{-} - ε$ . If $b \leq 0$ , the desired right side is nonpositive because $e (X, X) \geq 0$ and $2 (1 + ρ) α > 0$ . The left side is nonnegative by [F2], proving the claim in this case.

2.2givenF3step 1.1

Suppose $b > 0$ . Using [F3], $∣ X ∣ / n \leq ρ α$ , and $d^{*} ∣ X ∣ \geq 0$ , we obtain $e (X, X) \leq d^{*} ∣ X ∣ (∣ X ∣ / n + α) \leq (1 + ρ) α d^{*} ∣ X ∣$ . This remains valid when $d^{*} = 0$ or $X$ is empty.

3.1F4step 1.1step 2.1step 2.2∎

By [F4], step 1.1, and $b d^{*} ∣ X ∣ \geq 0$ , $e (X, Y^{c}) \geq b (d^{*} / n) ∣ X ∣ ∣ Y^{c} ∣ \geq b d^{*} ∣ X ∣ / 2$ . Step 2.2 and positivity of $2 (1 + ρ) α$ now give $e (X, Y^{c}) \geq b e (X, X) / (2 (1 + ρ) α)$ , as required. Together with step 2.1, this proves the claim.

Source notes

The statement and the combination of the two mixing bounds are attributed to Lemma 3.8 of Expander graphs are globally synchronizing. The proof separates the nonpositive coefficient case and uses the local suppliers; the article is not a proof premise.

Depends on

Used by · 1

Strict forms of the nested mixing estimates — Remark 3.9

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 p. 21, Lemma 3.8 and proof