PropositionStatement: AI-adaptedProof: 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.

Quantitative two-sided expansion — Proposition 6.9

PDF p. 36: Proposition 6.9, equations (6.7) and (6.8); PDF p. 37: Proposition 6.9 and proof; PDF p. 38: Proof of Proposition 6.9

Statement

The article asserts the following. For every $0 < ε < 1$ and $1 + ε < γ < 1 + ε^{- 2}$ , there is a constant $C = C (γ, ε) > 0$ such that, for $p = γ \log n / n$ , $d^{*} = γ \log n$ and $α = 8 (γ \log n)^{- 1 / 2}$ , the random graph $G (n, p)$ is an $(n, d^{*}, α, c^{-}, c^{+})$ -expander with probability at least $1 - C (\log n)^{4} n^{- ε}$ . Here $h (x) = (1 + x) \log (1 + x) - x$ for $x > - 1$ ; $c^{-} < 0$ and $c^{+} > 0$ are the shifted roots defined by $γ h (c^{-} - ε) = 1 + ε$ and $γ h (c^{+} + ε) = 1 + ε$ , respectively.

This assertion is false. At $γ = 2$ and $ε = 1 / 2$ , the probability of the stated expander event tends to zero as $n \to \infty$ .

In this statement $G (n, p)$ is the loop-free graph on $n$ vertices whose unordered edges occur independently with probability $p$ . The expander predicate requires $∥ A - p J ∥ \leq α d^{*}$ and $c^{-} d^{*} I ⪯ Δ_{L} ⪯ c^{+} d^{*} I$ , where $A$ is adjacency, $D$ is the diagonal degree matrix, $Δ_{L} = D - A - d^{*} I + p J$ , $J$ is the all-ones matrix, and $⪯$ denotes quadratic-form order.

Facts & Assumptions

[F1]

The graph law, shifted roots, and expander predicate have the meanings in Erdős–Rényi random graph and high probability, Shifted rate roots for quantitative expansion, and Two-sided spectral expander — Definition 1.9.

[F2]

At $γ = 2$ and $ε = 1 / 2$ , the expander probability is at most $η_{n} = 2 e^{4} \log n / \sqrt{n} + 2 p / (1 - p)^{2}$ , where $p = 2 \log n / n$ and $η_{n} \to 0$ . For every fixed $C > 0$ , the proposed failure bound $C (\log n)^{4} n^{- 1 / 2}$ tends to zero (Two fixed-parameter expander events have vanishing success probabilities).

Proof

Given: The parameters and graph law in the Statement.

Goal: Refute the attributed probability assertion.

1.1F1F2givenalgebra

The choice $ε = 1 / 2$ , $γ = 2$ satisfies $0 < ε < 1$ and $1 + ε < γ < 1 + ε^{- 2}$ , since $3 / 2 < 2 < 5$ . For all sufficiently large $n$ , $p = 2 \log n / n$ lies in $(0, 1)$ . By [F1] the event in [F2] is exactly the event in the attributed assertion at these parameters.

2.1F2step 1.1algebra∎

By [F2], its probability tends to zero. If the attributed assertion held for some fixed $C > 0$ , its lower bound would tend to one. These two limits are incompatible, so no such constant exists for this admissible parameter pair.

Source attribution

The assertion and its notation are attributed to Proposition 6.9 of the cited article. The refutation uses the separate local counterexample supplier; it does not use the article's assertion as a premise.

Depends on

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.

Sources

Expander graphs are globally synchronizing · PDF pp. 36–38, Proposition 6.9, equations (6.7)–(6.8), and proof