CounterexampleConstruction: AI-adaptedVerification: 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.

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

PDF p. 31: Section 6, equation (6.1)

Statement refuted

The assertion under examination is that, for every sequence $p_{n} = γ \log n / n$ with fixed $γ > 1$ , the simple graph $G (n, p_{n})$ satisfies $∥ A_{n} - p_{n} J ∥ \leq 2 \sqrt{n p_{n} (1 - p_{n})} + r_{n}$ with high probability for some deterministic $r_{n} = o (n^{- 1 / 44})$ . A counterexample is $p_{n} = 3 \log n / (2 n)$ for all sufficiently large $n$ (define the finitely many earlier probabilities arbitrarily in $[0, 1]$ ). With $g = 9 / (2 \sqrt{5}) - 2 > 0$ , this law instead has $∥ A_{n} - p_{n} J ∥ \geq (2 + g / 2) \sqrt{n p_{n}}$ with high probability. This refutes the displayed spectral assertion throughout that near-threshold range; it asserts no failure of a synchronization theorem.

Statement references

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

Centered graph matrices and reference degree

Asymptotic quantifiers and uniform parameter ranges

Loop-free Bernoulli adjacency and its two centerings

A negative adjacency eigenvalue survives all-ones centering

A rational entropy test above the critical degree ratio two

The deterministic critical degree root stays above nine quarters

A fixed outlier gap dominates the critical-source error

Facts & Assumptions

[F1]

The original article reports equation (6.1) and discusses $p = γ \log n / n$ with $γ > 1$ on PDF p. 31. This records attribution, not a premise establishing the estimate.

[F2]

For $d_{n} = (3 / 2) \log n$ and $K = 2 π > 0$ , the deterministic root $β_{n}$ exists for large $n$ , exceeds $9 / 4$ , and $p_{n} = d_{n} / n \to 0$ . The deterministic critical degree root stays above nine quarters

[F3]

The source lower-edge estimate in External input is Corollary 2.4(i) for the uncentered loop-free adjacency matrix; all its model and parameter hypotheses must hold.

[F4]

The exact loop-free mean is $p (J - I)$ , while the article reference centering is $Δ = A - p J$ . The outlier transfer needs this latter matrix and gives a norm lower bound from a negative adjacency eigenvalue. Loop-free Bernoulli adjacency and its two centerings A negative adjacency eigenvalue survives all-ones centering A fixed outlier gap dominates the critical-source error

External input

Alt–Ducatez–Knowles, Section 2, Corollary 2.4(i), PDF p. 6, supplies the following independent input. For the zero-diagonal adjacency matrix $A$ of $G (n, d / n)$ , take $κ = θ = 1 / 10$ and $a = 1 / 2 - κ = 2 / 5$ . If $(\log n)^{5 / 6} \leq d \leq n / 2$ , let $β_{1} (d) \geq 1$ solve $d I (β_{1}) + (1 / 2) \log (2 π β_{1} d) = \log n$ . Whenever $β_{1} (d) \geq 2 + (\log d)^{- 2 / 5}$ , there are fixed constants $C, c > 0$ such that, with probability $1 - o (1)$ , $∣ λ_{\min} (A) / \sqrt{d} + Λ (β_{1} (d)) ∣ \leq C (d^{- c (Λ (β_{1} (d)) - 2)} + d^{- 1 / 20})$ . The source also requires $1 \leq n / (C_{0} \sqrt{d})$ for the definition of $β_{1}$ , with a fixed universal $C_{0}$ ; this holds in the application. This is an external premise, not a reconstructed proof.

Counterexample

Given: The data and hypotheses in the Statement refuted.

Goal: Exhibit an applicable graph-law sequence for which the stated estimate fails.

1.1F2F3algebra

Let $p_{n} = d_{n} / n$ with $d_{n} = (3 / 2) \log n$ . By [F2], this is eventually a valid probability, $d_{n} \to \infty$ , and $β_{n} > 9 / 4$ . For the source parameters $κ = θ = 1 / 10$ , the degree requirement is $(\log n)^{5 / 6} \leq d_{n} \leq n / 2$ , which holds eventually. Also $n / \sqrt{d_{n}} \to \infty$ , and $β_{n} > 9 / 4 > 2 + (\log d_{n})^{- 2 / 5}$ eventually, so $l = 1$ is in the source index range. The simple graph model in the Statement is exactly the source model, including its zero diagonal.

2.1F3F4step 1.1algebra

By [F3] and step 1.1, there are events $E_{n}$ with $P (E_{n}) \to 1$ on which the least adjacency eigenvalue has the error estimate in External input, with $θ = 1 / 10$ . Apply [F4] and the outlier-error transfer to obtain $∥ A_{n} - p_{n} J ∥ \geq (2 + g / 2) \sqrt{d_{n}}$ with high probability. In particular the diagonal convention causes no loss: subtracting the positive semidefinite matrix $p_{n} J$ only strengthens the negative quadratic-form lower bound for the norm.

3.1F1F2step 2.1algebra∎

For any deterministic $r_{n} = o (n^{- 1 / 44})$ , one has $r_{n} / \sqrt{d_{n}} \to 0$ and $2 \sqrt{1 - p_{n}} \leq 2$ . Thus eventually $2 \sqrt{d_{n} (1 - p_{n})} + r_{n} < (2 + g / 2) \sqrt{d_{n}}$ . The event in the assertion refuted is then disjoint from the event in step 2.1, whose probability tends to one; its own probability tends to zero. This proves the counterexample for the article range $γ = 3 / 2 > 1$ .

Source notes

The five preceding local lemmas supply the convention transfer, norm monotonicity, explicit entropy gap, deterministic degree root and decay of the source error. The substantial remaining spectral input is imported precisely from Alt–Ducatez–Knowles. The counterexample challenges only the spectral assertion attributed in original equation (6.1). The original-article final assessor must independently compare and classify this lead; this authoring proposal does not enter a defect report or supply independent review.

Depends on

Used by · 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.

External dependencies

Johannes Alt, Raphael Ducatez and Antti Knowles, Extremal eigenvalues of critical Erdos-Renyi graphs · Section 2, PDF pp. 4-6: model, Theorem 2.1, definition of beta_l(d) preceding Corollary 2.4, and Corollary 2.4(i)

Let A be the zero-diagonal adjacency matrix of G(N,d/N). Fix 0<kappa<1/2 and kappa<=theta<5/2, and assume (log N)^(4/(5-2theta))<=d<=N/2. Let a=1/2-kappa and let beta_l(d)>=1 solve d(beta log beta-beta+1)+(1/2)log(2 pi beta d)=log(N/l). For indices l with beta_l(d)>=2+(log d)^(-a), Corollary 2.4(i) bounds |lambda_(l+1)(A)-sqrt(d)Lambda(beta_l(d))|+|lambda_(N+1-l)(A)+sqrt(d)Lambda(beta_l(d))| by C(d^(-c(Lambda(beta_l(d))-2))+d^(-theta/2))sqrt(d), with probability 1-o(1), where Lambda(t)=t/sqrt(t-1), c>0 is universal and C depends on kappa.

Hypotheses: Simple undirected graph: A=A*, A_xx=0; independent Bernoulli(d/N) variables for x<y. Fixed kappa in (0,1/2), kappa<=theta<5/2; displayed d-range; l within the deterministic L(d) set defined immediately before Corollary 2.4. For beta_l definition l<=N/(C sqrt d). The application uses kappa=theta=1/10, d=(3/2)log N, l=1; all conditions hold for sufficiently large N.

Reading limits: Read PDF pp.1-7, focusing on Section 2 model, full Theorem 2.1, full Corollary 2.3, beta_l definition, full Corollary 2.4 and Remarks 2.5-2.6. Inspected rendered images of PDF pp.4-6 to disambiguate centered versus uncentered A and the error exponent. Proofs in Sections 4-9 and Appendix D were not reconstructed or read in full. Only the explicitly stated lower-eigenvalue part of Corollary 2.4 is imported.

Sources

Expander graphs are globally synchronizing · PDF p. 31, Section 6, equation (6.1) and the following p=gamma log n/n paragraph; p. 6 for centering
Johannes Alt, Raphael Ducatez and Antti Knowles, Extremal eigenvalues of critical Erdos-Renyi graphs · Section 2, PDF pp. 4-6: model, Theorem 2.1, definition of beta_l(d) preceding Corollary 2.4, and Corollary 2.4(i)