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

The exact unshifted expansion event cannot have polynomial failure decay

Statement

Fix any $γ > 1$ and the unshifted roots $c^{-} \in (- 1, 0) < c^{+}$ of $γ ((1 + c) \log (1 + c) - c) = 1$ . Let $E_{n}$ be the event that $G (n, p)$ is an $(n, μ, 8 / \sqrt{μ}, c^{-}, c^{+})$ -expander, where $μ = γ \log n$ , $p = μ / n$ . There is $κ = κ (γ) > 0$ such that for all sufficiently large integers $n$ , $P (E_{n}^{c}) \geq \frac{κ}{\sqrt{\log n}} .$ Consequently no bound $P (E_{n}^{c}) \leq C (\log n)^{4} n^{- ε}$ can hold with fixed $C > 0$ and $ε > 0$ . In particular $γ = 2$ , $ε = 1 / 2$ is a counterexample under all original Theorem 6.2 parameter assumptions.

Facts & Assumptions

[F1]

The degree $k_{n} = ⌈ (1 + c^{-}) μ - p ⌉ - 1$ has bounded rounding from the lower entropy root, and its occurrence forces $E_{n}^{c}$ (The unshifted lower Laplacian bound excludes a boundary degree).

[F2]

At such a root, a degree- $k_{n}$ vertex exists with probability at least $κ / \sqrt{\log n}$ for some $κ > 0$ (A rare logarithmic degree occurs with probability of its first-moment order).

[F3]

For every $b > 0$ , $\log n / n^{b} \to 0$ (The logarithm grows more slowly than every positive real power).

Proof

Given: The fixed parameters and event in the Statement.

Goal: Obtain the lower bound and contradict the claimed rate.

1.1F1F2given

By [F1], the event in [F2] is contained in $E_{n}^{c}$ . Thus its probability lower bound proves the first displayed inequality. This uses the exact original centering and unshifted root, without any shifted-root assertion.

2.1F3step 1.1algebra∎

For any fixed $ε > 0$ , $n^{ε} / (\log n)^{9 / 2} \to \infty$ by [F3], for example by applying it with $b = ε / 9$ and taking the power $9 / 2$ . Hence $κ / \sqrt{\log n} > C (\log n)^{4} n^{- ε}$ eventually for every fixed $C > 0$ . The choice $ε = 1 / 2$ , $γ = 2$ satisfies $0 < ε < 1$ and $1 + ε < γ < 1 + ε^{- 2}$ because $3 / 2 < 2 < 5$ ; also $0 < p < 1$ eventually. Therefore this is a counterexample family under the complete original assumptions. It challenges the expansion probability only, not the separate synchrony event.

Depends on

Used by · 1

Quantitative Erdős–Rényi synchrony and the false exact-expansion rate — Theorem 6.2

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.