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

Failure of the stated constant-two expansion bound — Corollary 6.1

PDF p. 8: Use of Corollary 6.1 in proof of Theorem 1.2; PDF p. 32: Corollary 6.1

Statement

The article's Corollary 6.1 asserts that for every $ε > 0$ and every sequence $p = p (n) \geq (1 + ε) \log n / n$ , the graph $G (n, p)$ is with high probability an $(n, d^{*}, α, c^{-}, c^{+})$ -expander with $d^{*} = p n$ , $α \leq (2 + ε) (p n)^{- 1 / 2}$ and $- 1 < c^{-} < 0 < c^{+} < e - 1$ . Its use in the proof of Theorem 1.2 takes $c^{\pm}$ depending on the fixed $ε$ . This assertion is false: for a positive fixed $ε$ and an admissible sequence $p$ , even its required adjacency bound fails with probability tending to one.

Statement references

Two-sided spectral expander — Definition 1.9

Erdős–Rényi random graph and high probability

Asymptotic quantifiers and uniform parameter ranges

A near-threshold counterexample to the reported constant-two spectral bound

Facts & Assumptions

[F1]

In the two-sided expander definition, with adjacency matrix $A$ , all-ones matrix $J$ and $d^{*} = p n$ , the adjacency condition is $∥ A - p J ∥ \leq α p n$ (Two-sided spectral expander — Definition 1.9).

[F2]

For the simple graph $G (n, p)$ with $p = 3 \log n / (2 n)$ for sufficiently large $n$ , put $g = 9 / (2 \sqrt{5}) - 2 > 0$ . With high probability, $∥ A - p J ∥ \geq (2 + g / 2) \sqrt{p n}$ (A near-threshold counterexample to the reported constant-two spectral bound).

[F3]

The graph law has independent Bernoulli edge indicators and no loops; high probability means that the corresponding event probability tends to one as $n \to \infty$ (Erdős–Rényi random graph and high probability, Asymptotic quantifiers and uniform parameter ranges).

Proof

Given: The attributed assertion in the Statement and the inputs [F1]–[F3].

Goal: Exhibit a fixed positive $ε$ and an admissible sequence for which the asserted expander event has probability tending to zero.

1.1F2F3algebra

Choose $ε = g / 4$ . Since $g > 0$ and $g < 2$ , this choice lies in $(0, 1 / 2)$ . Set $p = 3 \log n / (2 n)$ for all sufficiently large $n$ , and choose any valid probabilities for the finitely many earlier indices. Then $p \geq (1 + ε) \log n / n$ eventually, and $p n > 0$ eventually. The graph sequence has the law required by [F2].

2.1F1F2step 1.1algebra∎

If the asserted expander event held for any parameters satisfying its inequalities, [F1] would give $∥ A - p J ∥ \leq (2 + ε) \sqrt{p n}$ . But $ε = g / 4 < g / 2$ , so this event is disjoint from the high-probability event in [F2]. Therefore its probability tends to zero, establishing the stated failure. The conclusion is independent of the choices of $c^{-}$ and $c^{+}$ .

Source notes

The article citation records the original assertion and its use; it is not a premise in the refutation. The completed counterexample supplier contains the independent spectral input and its hypothesis transfer. This refutation alone makes no claim about the truth of Theorem 1.2 or global synchronization.

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 page 32, Corollary 6.1; PDF page 8, proof of Theorem 1.2