TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-07

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.

Cheeger inequalities for finite regular graphs

Statement

For a finite $d$ -regular adjacency-slot multigraph on $n \geq 2$ vertices, $\frac{γ}{2} \leq h \leq \sqrt{2 γ}, h \leq h_{V} \leq d h .$ Here $γ = 1 - μ_{2}$ is the algebraic gap; it is not replaced by $1 - α$ .

Facts & Assumptions

Given: the objects and hypotheses in the statement above.

[F1]

For a finite $d$ -regular graph on $n \geq 2$ vertices and a nonnegative $f$ supported on at most $n / 2$ vertices, use the unnormalized inner product $⟨ f, g ⟩_{0} = \sum_{v} f (v) g (v)$ and energy $E (f) = ⟨ f, (I - M) f ⟩_{0}$ . Then $h ∥ f ∥_{0}^{2} \leq \frac{1}{d} \sum_{u < v} A_{u v} ∣ f (u)^{2} - f (v)^{2} ∣ \leq \sqrt{2 E (f) ∥ f ∥_{0}^{2}} .$ Also $γ \leq 2 h$ , and there exists a nonzero nonnegative function $g$ , supported on at most $n / 2$ vertices, with $E (g) \leq γ ∥ g ∥_{0}^{2}$ : namely, the positive part of a suitable sign of a nonzero mean-zero $μ_{2}$ eigenvector. These are the indicator and positive-part conclusions of the preceding lemma in the unnormalized inner product. (Cheeger sweep and layer cake).

Proof

1.1F1

Take the nonzero positive part with $E (f) \leq γ ∥ f ∥_{0}^{2}$ and combine it with the sweep estimate. Since $∥ f ∥_{0}^{2} > 0$ , this yields $h \leq \sqrt{2 γ}$ . The indicator estimate in the same cited result gives $γ / 2 \leq h$ . Zero gap is permitted and forces $h = 0$ .

2.1step 1.1algebra∎

For any nonempty eligible $S$ , each vertex of $\partial_{V} S$ receives at least one and at most $d$ cut slots. Thus $cut (S) / d \leq ∣ \partial_{V} S ∣ \leq cut (S)$ . The first inequality divided by $∣ S ∣$ and minimized gives $h \leq h_{V}$ . Apply the second to a set minimizing $h$ to obtain $h_{V} \leq d h$ . The eligible collection is nonempty and finite because $n \geq 2$ ; loops never cross its cuts.

Depends on

Cheeger sweep and layer cake

Used by

Expander independent sets coloring and diameter Corollary
Expander size adjustment and laziness Lemma

Dependency tree · two levels

3 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §4.5 Theorem4.11 (also Theorem2.4), pp40–42. (standard reference, not scraped)