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 walk hits dense bad sets

Example

On a Margulis graph, a fixed bad vertex set of density at least $1 / 4$ is missed by a stationary $t$ -step walk with probability at most $(3 / 4) (313 / 320)^{t}$ , for $t \geq 0$ . The stationary-start requirement cannot simply be deleted.

Facts & Assumptions

Given: the objects and hypotheses in the statement above.

[F1]

Let $α < 1$ and let $B$ be a fixed vertex set of density $δ \in [0, 1]$ . For a walk begun from the uniform distribution and taking $t \geq 0$ steps (thus sampling $t + 1$ vertices), $\Pr [no visit to B] \leq (1 - δ) [1 - (1 - α) δ]^{t} \leq (1 - δ) e^{- (1 - α) δ t} .$ A zeroth power is interpreted as one even when its base is zero. (Expander walk hits dense bad sets).

[F2]

For every $m \geq 2$ the normalized Margulis adjacency has absolute nontrivial norm $α \leq 73 / 80$ , hence algebraic gap at least $7 / 80$ . For $m = 1$ the mean-zero space is zero and $α = 0$ . (Margulis family has uniform spectral gap).

Verification

1.1

The Margulis bound gives $1 - α \geq 7 / 80$ . In the avoidance estimate, $1 - δ \leq 3 / 4$ and $1 - (1 - α) δ \leq 1 - (7 / 80) (1 / 4) = 313 / 320$ . All factors are nonnegative, so multiplication yields the displayed estimate, including $t = 0$ .

F1F2

2.1

For a concrete start issue take modulus $m = 2$ and let $B$ be one of the four vertices. A deterministic start outside $B$ misses at time zero with probability one, whereas the stationary formula gives $3 / 4$ . Thus it does not hold unchanged for arbitrary starts. On the singleton graph a set of density at least $1 / 4$ is the full set and avoidance is zero.

step 1.1algebra∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

5 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 Theorem3.6 and Chapter8 weaker bound; numerical specialization. (standard reference, not scraped)