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

Convex adjacency norm: sharp coordinate constant and median counterexample

PDF p. 35: Proof of Corollary 6.6

Statement

Let $n \geq 2$ , $0 < p < 1$ , and let $X$ consist of the $d = (\binom{n}{2})$ independent Bernoulli- $p$ edge coordinates of the loop-free graph $G (n, p)$ . Let $T (x)$ have zero diagonal and symmetric off-diagonal coordinates $x$ , let $J$ be the all-ones matrix, and use the Euclidean coordinate metric and Euclidean operator norm. The function $f (x) = ∥ T (x) - p J ∥$ is convex; its sharp Lipschitz constant on $[0, 1]^{d}$ is $\sqrt{2 (n - 1) / n}$ , which exceeds 1 for $n \geq 3$ .

The article's accompanying bound $M ∥ Δ_{A} ∥ \leq 4 \sqrt{n p (1 - p)} + 4$ for every $n \geq 1000$ and $p \in (0, 1)$ is false. Specifically, at $k = 100$ , $n = 4^{k + 2} k!$ , $p = 1 / n$ , every median of $∥ Δ_{A} ∥ = ∥ A - p J ∥$ is at least 9, whereas $4 \sqrt{n p (1 - p)} + 4 < 8$ . Here a median $M Z$ means any real number with both $P (Z \leq M Z) \geq 1 / 2$ and $P (Z \geq M Z) \geq 1 / 2$ .

Statement references

The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖

Convex and strictly convex functions on Euclidean convex sets

Lipschitz map, α-Hölder map for rational 0 < α ≤ 1, and contraction

Facts & Assumptions

[F1]

The loop-free graph law has independent Bernoulli edge coordinates (The Erdős-Rényi finite random graph G(n,p)).

[F2]

The article chooses $Δ_{A} = A - p J$ for $G (n, p)$ (Centered graph matrices and reference degree).

[F3]

The affine norm map is convex and has sharp cube Lipschitz constant $\sqrt{2 (n - 1) / n}$ (The sharp coordinate constant already occurs inside the Bernoulli cube).

[F4]

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

[F5]

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

Proof

Given: The hypotheses and objects in the Statement.

Goal: Establish the asserted conclusions.

1.1F1F2F3given

The edge-coordinate representation is [F1], with the centering identified by [F2]. Apply [F3] to obtain the asserted convexity and sharp Lipschitz constant. Its explicit two points lie in the actual cube; hence replacing the global domain by the Bernoulli coordinate cube does not restore the 1-Lipschitz assertion.

2.1F1F2F4F5givenalgebra∎

Choose $k = 100$ and the displayed $n, p$ . Then $n$ is an even integer exceeding 1000 and $0 < p < 1$ , so the original median assertion applies to these parameters. By [F4] and [F5], $Z = ∥ Δ_{A} ∥ \geq 9$ on an event of probability at least $4 / 5$ . If $m < 9$ , then $P (Z \leq m) \leq 1 / 5 < 1 / 2$ . Consequently every median is at least 9. Meanwhile $n p (1 - p) = 1 - 1 / n < 1$ , so $4 \sqrt{n p (1 - p)} + 4 < 8$ . This is a concrete counterexample under the original hypotheses.

Source notes

The original article, PDF p. 35, proof of Corollary 6.6, says “It is not hard to see that f is convex and 1-Lipschitz” and then states the median bound refuted above. The definitions of $J$ , $Δ_{A}$ , the choice $d^{*} = p n$ , and the operator norm are in Section 1.2, PDF p. 6; the independent-edge model is described on PDF p. 4.

The local proof establishes the sharp coordinate constant and the counterexample to the displayed median bound under its full original quantifiers.

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 — Abdalla, Bandeira, Kassabov, Souza, Strogatz, Townsend (2026) · PDF p. 35, Proof of Corollary 6.6