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

Uniform small centered adjacency above logarithmic mean degree

Statement

For $n \geq 3$ , $0 \leq p \leq 1$ and $d = n p \geq \log n$ , let $A$ be the adjacency matrix of the loop-free $G (n, p)$ and $J$ the all-ones matrix. Set $K = 1 + e^{2 / 3} (2 \sqrt{2} + 42)$ . Then $E ∥ A - p J ∥ \leq K \sqrt{d}, P (∥ A - p J ∥ \geq d^{3 / 4}) \leq K d^{- 1 / 4} .$ The bounds hold for every admissible $p$ with the same constant $K$ .

Facts & Assumptions

[F1]

The graph law is Erdős–Rényi random graph and high probability. For an independent copy $A^{'}$ , actual-mean symmetrization gives $E ∥ A - p J ∥ \leq E ∥ A - A^{'} ∥ + p$ in the Euclidean operator norm (Norm symmetrization at the actual matrix mean).

[F2]

The bounded symmetric expectation lemma is Bounded symmetric matrix expectation at the variance scale. For a nonnegative finite-space variable $Y$ and $t > 0$ , $P (Y \geq t) \leq E Y / t$ (Markov's inequality on a finite probability space).

[F3]

In vertex order $1, \dots, n$ , the adjacency entries are the unordered-edge indicators off the diagonal and zero on the diagonal; the matrix is symmetric (The adjacency matrix of a finite simple graph). We use the operator norm on $R^{n}$ with $∥ v ∥_{2} = (\sum_{i} v_{i}^{2})^{1 / 2}$ , namely $∥ B ∥ = \max_{∥ v ∥_{2} = 1} ∥ B v ∥_{2}$ (The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖). In particular $∥ I ∥ = 1$ , since $I v = v$ .

[F4]

The product of two finite graph probability spaces has outcome weights $w (g) w (g^{'})$ (The finite product of finite probability spaces). These weights normalize, and events depending on distinct graph coordinates have probabilities equal to the product of their marginal probabilities (Product weights normalize, and coordinate events are mutually independent).

[F5]

A finite probability space $(Ω, w)$ has nonnegative outcome weights summing to one, and every subset $E \subseteq Ω$ is an event with $P (E) = \sum_{ω \in E} w (ω)$ (Finite probability spaces, outcome weights, events, and event probabilities). A real random variable is any function $Y : Ω \to R$ , with distribution given by the probabilities of its value fibres (Real random variables on finite probability spaces and their finite distributions). Its scalar expectation is $E Y = \sum_{ω \in Ω} Y (ω) w (ω)$ (Expectation of a real random variable on a finite probability space). This applies to the matrix entries, their squares and the matrix norms used below.

Proof

Given: The graph and $d \geq \log n$ in the Statement.

Goal: Prove the uniform bounds.

1.1F1F3F4F5given

On the product in [F4], let $A$ and $A^{'}$ be the adjacency matrices of the first and second graph coordinates and set $X = A - A^{'}$ . The coordinate-event theorem gives independent copies with the original graph law. For any set $S$ of unordered edges and any $a_{e}, b_{e} \in {0, 1}$ , put $q_{p} (0) = 1 - p$ and $q_{p} (1) = p$ . Independence between the graph coordinates and the edge-assignment formula within each graph give $P (A_{e} = a_{e}, A_{e}^{'} = b_{e} for all e \in S) = \prod_{e \in S} q_{p} (a_{e}) q_{p} (b_{e})$ . Here $A_{e}$ denotes either off-diagonal entry indexed by $e$ .

2.1F5step 1.1algebra

For $x_{e} \in {- 1, 0, 1}$ , sum the joint formula of step 1.1 over the assignments with $a_{e} - b_{e} = x_{e}$ . Distributivity of the finite sums gives $P (X_{e} = x_{e} for all e \in S) = \prod_{e \in S} (\sum_{a, b \in {0, 1} : a - b = x_{e}} q_{p} (a) q_{p} (b))$ . Each factor is the corresponding marginal probability, equal to $p (1 - p), 1 - 2 p (1 - p), p (1 - p)$ at $- 1, 0, 1$ , respectively. Thus the unordered-edge differences are mutually independent, also at $p = 1$ .

3.1F2F3F5step 2.1given

By [F3], $X$ is real symmetric with zero diagonal. By step 2.1 its lower-triangular entries are finite-valued, independent, symmetric in distribution about zero and bounded by one; adjoining the constant diagonal entries preserves independence. Each off-diagonal entry has mean zero and second moment, hence variance, $2 p (1 - p)$ . Therefore the parameter of the bounded symmetric expectation lemma is $s = \sqrt{2 (n - 1) p (1 - p)} \leq \sqrt{2 d}$ .

4.1F1F2F3F5step 3.1

The bounded symmetric expectation estimate and [F1] give $E ∥ A - p J ∥ \leq p + e^{2 / 3} (2 \sqrt{2 d} + 42 \sqrt{\log n}) \leq K \sqrt{d}$ , because $p \leq 1 \leq \sqrt{d}$ for $n \geq 3$ . This also handles $p = 1$ , when $X = 0$ and $A - p J = - I$ .

5.1F2F3F5step 4.1∎

Apply Markov to $Y = ∥ A - p J ∥$ at $t = d^{3 / 4} > 0$ to obtain the probability bound. Every preceding inequality is finite- $n$ and holds for all the allowed $p$ , so no fixed-density asymptotic is being used uniformly without justification.

Depends on

Used by · 1

Uniform two-sided expansion sufficient for global synchrony

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.