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.

Total incident edge bounds — Lemma 3.6

PDF p. 20: Lemma 3.6 and following prose

Statement

Let $G = (V, E)$ be an $(n, d^{*}, α, c^{-}, c^{+})$ -expander, and let $X \subseteq V$ have density $ρ = ∣ X ∣ / n$ . Here $n = ∣ V ∣ > 0$ , $X^{c} = V ∖ X$ , and $e (X, Y) = \sum_{x \in X} \sum_{y \in Y} A_{x y}$ counts ordered adjacency entries, including a loop once. Then

$(1 + c^{-} (1 - ρ) - α) d^{*} ∣ X ∣ \leq e (X, V) \leq (1 + c^{+} (1 - ρ) + α) d^{*} ∣ X ∣ .$

In particular, if $d_{\max} (G) = \max_{x \in V} \sum_{y \in V} A_{x y}$ , then $d_{\max} (G) \leq (1 + c^{+} + α) d^{*}$ .

Facts & Assumptions

[F1]

The two-sided expander has a nonempty finite vertex set, is also an $(n, d^{*}, α)$ -expander, and satisfies $Δ_{L} ⪯ c^{+} d^{*} I$ , where $Δ_{L} = L - d^{*} I + (d^{*} / n) J$ and $L = D - A$ (Two-sided spectral expander — Definition 1.9, Adjacency spectral expander — Definition 1.3).

[F2]

The degree is the row sum of $A$ , $D$ is the diagonal degree matrix, and $J$ has all entries equal to one; $d_{\max}$ is the maximum degree (Adjacency, degrees, graph Laplacian, and spectral notation). The ordered edge count is the stated finite sum (Oriented edge count between sets).

[F3]

For Hermitian matrices, $B ⪯ C$ means $f^{*} (C - B) f \geq 0$ for every complex vector $f$ (Loewner order, Hermitian inner product, and operator norm).

[F4]

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

[F5]

The cut bound gives $c^{-} (d^{*} / n) ∣ X ∣ ∣ X^{c} ∣ \leq e (X, X^{c}) - (d^{*} / n) ∣ X ∣ ∣ X^{c} ∣ \leq c^{+} (d^{*} / n) ∣ X ∣ ∣ X^{c} ∣$ (Cut-edge mixing bound — Lemma 3.4).

[F6]

For disjoint finite sets, cardinality is additive and a finite real-valued sum over their union splits into the sums over the two sets (The sum rule: a finite disjoint union is finite with | A ∪ B| = | A| + | B| and |⋃_i ∈ I Aᵢ| = ∑_i ∈ I| Aᵢ|, and a sum over a finite index set splits along a partition, clauses 1 and 3).

Proof

Given: An $(n, d^{*}, α, c^{-}, c^{+})$ -expander $G$ and $X \subseteq V$ .

Goal: Prove the two incident-edge bounds and the maximum-degree consequence.

1.1F1F2F4F5F6algebra

The disjoint partition $V = X \cup X^{c}$ , the finite-sum definition, and [F6] give $e (X, V) = e (X, X) + e (X, X^{c})$ . Add the respective lower bounds in [F4] and [F5], and then add the respective upper bounds. By [F6], $∣ X ∣ + ∣ X^{c} ∣ = n$ ; hence $∣ X^{c} ∣ / n = 1 - ρ$ , and the two sums simplify to the two bounds in the statement. This calculation also covers $X = \emptyset$ and $X = V$ .

1.2F1F2F3algebra

Let $1$ be the vector of ones. The row-sum definition of $D$ gives $L 1 = 0$ , while $J 1 = n 1$ ; hence $Δ_{L} 1 = 0$ . Applying $Δ_{L} ⪯ c^{+} d^{*} I$ to $1$ yields $0 \leq c^{+} d^{*} n$ , so $c^{+} d^{*} \geq 0$ because $n > 0$ .

2.1F1F2step 1.1step 1.2algebra∎

For any $x \in V$ , take $X = {x}$ in step 1.1. Then $e (X, V) = d (x)$ and $ρ = 1 / n$ , so $d (x) \leq (1 + c^{+} + α) d^{*} - (c^{+} d^{*}) / n \leq (1 + c^{+} + α) d^{*}$ . Taking the maximum over the nonempty finite set $V$ proves the consequence.

Source notes

The statement and the addition of the internal and cut estimates are attributed to Lemma 3.6 and the following prose of Expander graphs are globally synchronizing. The proof uses the declared mathematical suppliers.

Depends on

Used by · 1

Almost antisymmetry and summed kernel bounds

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. 20, Lemma 3.6 and following prose