ExampleConstruction: AI-adaptedVerification: 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.

Expander mixing lemma

Example

For the looped complete adjacency-slot graph $A = J_{n}$ , $d = n$ and $α = 0$ , with $e (S, T) = ∣ S ∣ ∣ T ∣$ for all sets. In contrast, for $K_{r, r}$ with $r \geq 2$ one has $μ_{2} = 0$ but $α = 1$ .

Facts & Assumptions

Given: the objects and hypotheses in the statement above.

[F1]

For any subsets $S, T$ of a finite $d$ -regular adjacency-slot graph on $n \geq 1$ vertices, let $e (S, T) = \sum_{u \in S, v \in T} A_{u v}$ count ordered slots. Then $∣ e (S, T) - \frac{d ∣ S ∣ ∣ T ∣}{n} ∣ \leq α d \sqrt{∣ S ∣ (1 - ∣ S ∣ / n) ∣ T ∣ (1 - ∣ T ∣ / n)} .$ Overlap and loop slots are allowed. (Expander mixing lemma).

Verification

1.1

The normalized complete matrix sends every vector to its average constant vector, so it vanishes on the mean-zero space. There is one slot for every ordered pair, giving $e (S, T) = ∣ S ∣ ∣ T ∣$ even for overlapping sets. This is exact equality in mixing, including empty or full sets and $n = 1$ .

F1algebra

2.1

For $K_{r, r}$ , $M$ averages across the opposite side. Its constant vector has eigenvalue one; the vector $+ 1$ on one side and $- 1$ on the other has eigenvalue minus one. The $2 r - 2$ dimensional space with zero sum on each side has eigenvalue zero. These subspaces span, so $μ_{2} = 0$ for $r \geq 2$ , whereas the absolute nontrivial norm is one. A walk alternates sides, explaining why a positive algebraic gap alone does not give the absolute contraction used in mixing and walk estimates.

step 1.1algebra∎

Depends on

Expander mixing lemma

Used by

Nothing in the library uses this result yet.

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; §2.3 spectral properties and §2.4 mixing, pp20–21; finite computations. (standard reference, not scraped)