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.

Counterexamples to both centered-adjacency tail bounds in Corollary 6.6

PDF p. 35: Corollary 6.6; equations (6.5), (6.6)

Statement

Both bounds stated in the original Corollary 6.6 are false under their complete displayed quantifiers, for the loop-free independent-edge graph and the article's centering $Δ_{A} = A - p J$ .

First, the original assertion is that for every $p \in (0, 1)$ and $n \geq 1000$ , $P (∥ Δ_{A} ∥ \geq 4 \sqrt{n p (1 - p)} + 4 + t) \leq 2 \exp (- t^{2} / 4) (t > 0) .$ At $n = 4^{146} 144!$ , $p = 1 / n$ , $t = 3$ , its left side is at least $4 / 5$ and its right side is at most $8 / 13$ .

Second, the original assertion is that for every fixed $γ > 0$ there is $n_{0} (γ)$ such that, whenever $p = γ \log n / n$ and $n \geq n_{0} (γ)$ , $P (∥ Δ_{A} ∥ \geq 8 \sqrt{γ \log n}) \leq 2 n^{- γ} .$ At the single fixed value $γ = 10^{- 6}$ , every even integer $n$ with $\log n \geq 2000000$ violates this inequality: the left side exceeds $1 / 2$ , while the right side is at most $2 / 5$ . The left side in fact tends to one through even $n \to \infty$ . Thus no choice of $n_{0} (10^{- 6})$ can make the second assertion true. Norms are Euclidean operator norms, $J$ is the all-ones matrix, and $n^{- γ} = \exp (- γ \log n)$ .

Facts & Assumptions

[F1]

The random graph is the loop-free law with independent Bernoulli edges (The Erdős-Rényi finite random graph G(n,p)).

[F2]

The article centers it as $Δ_{A} = A - p J$ (Centered graph matrices and reference degree).

[F3]

At $n = 4^{k + 2} k!$ and $p = 1 / n$ , a vertex of degree at least $k$ occurs with probability at least $4 / 5$ (A large degree with explicitly bounded probability at fixed sparse density).

[F4]

A degree of at least $k$ gives $∥ A - J / n ∥ \geq \sqrt{k} - 1$ (A high-degree vertex forces a large centered adjacency norm).

[F5]

For $γ = 10^{- 6}$ and every even $n$ with $\log n \geq 2000000$ , the logarithmic tail probability exceeds $1 / 2 > 2 / 5 \geq 2 n^{- γ}$ and tends to one (The proposed small-gamma centered-adjacency tail has the opposite limit).

[F6]

The exponential series gives $\exp (x) \geq 1 + x$ for $x \geq 0$ (The real exponential function and the number e by a power series).

[F7]

The exponential is positive and $\exp (- x) = 1 / \exp (x)$ (The exponential is positive and satisfies exp(-x)=1/exp(x)).

[F8]

Every real number has an integer ceiling at least as large as itself (Ceilings give the least positive integer meeting a real threshold).

[F9]

The factorial $k!$ is the product of the integers from 1 to $k$ (The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ).

[F10]

The logarithm is inverse to the exponential (The natural logarithm as the inverse of the exponential function).

[F11]

The exponential is strictly increasing (The exponential function is strictly increasing).

[F12]

For a matrix $B$ acting on $R^{n}$ with its Euclidean inner product, $∥ B ∥ = \max_{∥ v ∥_{2} = 1} ∥ B v ∥_{2}$ (The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖).

[F13]

On a finite probability space $(Ω, w)$ , each outcome weight $w (ω)$ is nonnegative and every subset $E \subseteq Ω$ is an event with probability $P (E) = \sum_{ω \in E} w (ω)$ (Finite probability spaces, outcome weights, events, and event probabilities).

[F14]

In a finite simple graph, the degree of a vertex is the number of its neighbors, and the maximum degree is the largest of these numbers when the vertex set is nonempty (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

Proof

Given: The objects and hypotheses in the Statement.

Goal: Prove the asserted conclusions.

1.1F1F2F3F4F6F7F9F12F13F14givenalgebra

For the first inequality take $k = 144$ , $n = 4^{146} 144!$ , $p = 1 / n$ , $t = 3$ . These satisfy $n \geq 1000$ , $0 < p < 1$ and $t > 0$ . Let $E$ be the event that some vertex has degree at least $144$ , and let $T$ be the norm event in the first displayed inequality. By [F14], having at least $144$ neighbors is exactly having degree at least $144$ , so [F3] gives $P (E) \geq 4 / 5$ . On $E$ , [F4] gives $∥ Δ_{A} ∥ \geq 11$ , while the asserted threshold equals $4 \sqrt{1 - 1 / n} + 7 < 11$ , so $E \subseteq T$ . By [F13], $P (T) = P (E) + \sum_{ω \in T ∖ E} w (ω) \geq P (E)$ because all outcome weights are nonnegative. Thus the event in the first displayed inequality has probability at least $4 / 5$ . By [F6] and [F7], its proposed bound $2 \exp (- 9 / 4)$ is at most $2 / (1 + 9 / 4) = 8 / 13 < 4 / 5$ . This is a concrete counterexample to equation (6.5).

2.1F1F2F5F8F10F11F12givenconstruct∎

For the second inequality fix $γ = 10^{- 6}$ once and for all. Apply [F5] at every even integer $n$ with $\log n \geq 2000000$ . These are applicable counterexamples with valid graph probabilities. Given any proposed cutoff $n_{0} (10^{- 6})$ , put $B = \max {1, n_{0} (10^{- 6}), \exp (2000000)}$ and choose $n = 2 ⌈ B / 2 ⌉ + 2$ . By [F8] this is an even positive integer greater than $B$ . By [F10] and [F11], $\log n > 2000000$ . Increasing $B$ gives arbitrarily large such integers. The contradiction therefore persists beyond every cutoff. The limit in [F5] also proves the stated asymptotic behavior, rather than merely failure at a bounded set of sizes.

Source notes

The original PDF p. 35, Corollary 6.6, states (6.5) “For any $p \in (0, 1)$ and $n \geq 1000$ ” and (6.6) “for every $γ > 0$ , there is $n_{0} (γ)$ ”. Both complete claims are retained above and refuted separately. The original page image and extracted text were inspected, together with Section 1.2, PDF p. 6, fixing the centering and norm. The sparse-degree and logarithmic-tail lemmas supply independent local counterexamples. No concentration theorem or expected-norm claim is used as a premise. This result refutes the unrestricted $γ > 0$ statement, not every possible larger- $γ$ variant, and it does not by itself refute the article's main synchronization statements, which impose other parameter ranges.

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 p. 35, Corollary 6.6, equations (6.5), (6.6) and proof