LemmaStatement: 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.

Expander walk restricted operator

Statement

Let $S$ have density $β = ∣ S ∣ / n$ in a finite regular graph and let $P_{S}$ project onto functions supported in $S$ . Then $∥ P_{S} M P_{S} ∥ \leq α + (1 - α) β .$ For a stationary length- $t$ walk, $t \geq 0$ , its confinement probability is $n^{- 1} ⟨ 1_{S}, (P_{S} M P_{S})^{t} 1_{S} ⟩_{0}$ , where the inner product is unnormalized.

Facts & Assumptions

Given: the objects and hypotheses in the statement above.

[F1]

A walk that at each step chooses one of the $d$ ports uniformly has transition matrix $M$ and stationary uniform law $u = 1 / n$ . For any initial probability vector $p$ and integer $t \geq 0$ , using the ordinary Euclidean norm, $∥ M^{t} p - u ∥_{2} \leq α^{t} ∥ p - u ∥_{2}, TV (M^{t} p, u) \leq \frac{\sqrt{n}}{2} α^{t} .$ For $t = 0$ the factor $α^{0}$ is interpreted as one. For $t \geq 1$ , the adjacency-slot power has nontrivial norm $α^{t}$ . Here total variation means half the $ℓ^{1}$ distance. (Expander walk contraction).

Proof

1.1F1algebra

For $f$ supported in $S$ , let $J f$ be its constant projection. Finite-sum Cauchy–Schwarz gives $∥ J f ∥^{2} \leq β ∥ f ∥^{2}$ . Write $f = J f + f_{0}$ with orthogonal parts. Since $M$ fixes the constant part and contracts the other by $α$ , the Rayleigh form is at most $∥ J f ∥^{2} + α ∥ f_{0} ∥^{2} \leq [α + (1 - α) β] ∥ f ∥^{2}$ and at least $- α ∥ f ∥^{2}$ . The supported symmetric compression has an orthonormal eigenbasis, so its absolute norm has the asserted bound; outside that space it is zero.

2.1F1step 1.1∎

Expand the matrix product: each factor $P_{S}$ deletes precisely the paths with a vertex outside $S$ , and each $M$ factor supplies its step probability. Summing endpoints with the factor $1 / n$ gives uniform initial sampling. For $t = 0$ the expression is $∣ S ∣ / n$ ; if $S$ is empty it is zero and if $S = V$ it is one. These statements also cover $n = 1$ .

Depends on

Expander walk contraction

Used by

Expander walk sampled and moving sets Proposition
Expander walk hits dense bad sets Theorem

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; §3.2 Lemmas3.7–3.8, pp28–29; sharpened constant from the same projection proof. (standard reference, not scraped)