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.

Degree bounds from two-sided expansion — Lemma 3.1

PDF p. 18: Lemma 3.1

Statement

If $G$ is an $(n, d^{*}, α, c^{-}, c^{+})$ -expander, then $(1 + c^{-}) d^{*} - d^{*} / n \leq d_{\min} (G) \leq d_{\max} (G) \leq (1 + c^{+}) d^{*} + 1 - d^{*} / n$ .

Here the expander predicate, including its centered Laplacian inequalities, is as in Two-sided spectral expander — Definition 1.9; degrees and their extrema use Adjacency, degrees, graph Laplacian, and spectral notation. In particular, $n > 0$ , the adjacency matrix is binary, and a loop contributes once to its vertex's degree.

Facts & Assumptions

[F1]

For the expander, $c^{-} d^{*} I ⪯ Δ_{L} ⪯ c^{+} d^{*} I$ , where $Δ_{L} = L - d^{*} I + (d^{*} / n) J$ and $L = D - A$ (Two-sided spectral expander — Definition 1.9). The order is the quadratic-form order on Hermitian matrices (Loewner order, Hermitian inner product, and operator norm).

[F2]

The graph has a nonempty finite vertex set $V$ , $D_{x x} = d (x)$ , $A_{x x} \in {0, 1}$ , and $d_{\min} (G)$ and $d_{\max} (G)$ are the minimum and maximum of the degrees (Adjacency, degrees, graph Laplacian, and spectral notation).

[F3]

If a Hermitian matrix $B$ satisfies $a I ⪯ B ⪯ b I$ , then $a \leq B_{x x} \leq b$ for every vertex $x$ (Self-adjoint order, norm bounds and diagonal tests).

Proof

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

Goal: Establish the stated chain of degree bounds.

1.1F1F2F3algebra

The matrices in [F1] are real symmetric and hence Hermitian. Applying the diagonal test [F3] to the two inequalities in [F1] gives $c^{-} d^{*} \leq (Δ_{L})_{x x} \leq c^{+} d^{*}$ for each $x \in V$ . Since $J_{x x} = I_{x x} = 1$ , [F1] and [F2] give $(Δ_{L})_{x x} = d (x) - A_{x x} - d^{*} + d^{*} / n$ . Thus $(1 + c^{-}) d^{*} - d^{*} / n + A_{x x} \leq d (x) \leq (1 + c^{+}) d^{*} - d^{*} / n + A_{x x}$ .

2.1F2step 1.1algebra∎

By [F2], $0 \leq A_{x x} \leq 1$ , so every degree lies between $(1 + c^{-}) d^{*} - d^{*} / n$ and $(1 + c^{+}) d^{*} + 1 - d^{*} / n$ . Taking the minimum and maximum over the nonempty finite set $V$ yields the outer bounds, while the minimum is at most the maximum. This proves the displayed chain.

Source notes

The statement is attributed to Lemma 3.1 of Expander graphs are globally synchronizing; the argument above rests on the stated mathematical suppliers.

Depends on

Used by · 1

The original shifted roots impose a minimum degree above log n

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. 18, Lemma 3.1