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.

Normalize the logarithmic random graph for nonbacktracking estimates

Statement

Fix $γ > 1$ , put $L = \log n$ , $μ = γ L$ , $p = μ / n$ , and let $A$ be the adjacency matrix of $G (n, p)$ . For all sufficiently large integers $n$ , $0 < p < 1$ and $H = (A - E A) / \sqrt{μ}$ is real symmetric with independent mean-zero upper-triangular entries, zero diagonal, and $\max_{i} \sum_{j} E ∣ H_{i j} ∣^{2} \leq 1, \max_{i, j} E ∣ H_{i j} ∣^{2} \leq 1 / n, \max_{i, j} ∣ H_{i j} ∣ \leq 1 / \sqrt{μ} .$ Also $E A = p (J - I)$ , $A - p J = \sqrt{μ} H - p I$ , and $1 \leq q = \sqrt{μ} \leq n^{1 / 10}$ eventually.

Facts & Assumptions

[F1]

For $G (n, p)$ , $A_{i j} = A_{j i}$ for $i \neq j$ is the indicator of the unordered edge ${i, j}$ , and $A_{i i} = 0$ . The indicators for distinct unordered edges are independent Bernoulli $(p)$ variables, taking values $1$ and $0$ with probabilities $p$ and $1 - p$ , respectively (The Erdős-Rényi finite random graph G(n,p), The adjacency matrix of a finite simple graph, Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials).

[F2]

Expectation on a finite probability space is the weighted sum over its outcomes (Expectation of a real random variable on a finite probability space).

[F3]

The article centers the adjacency matrix at $p J$ (Centered graph matrices and reference degree).

[F4]

For every $a > 0$ , $\log n / n^{a} \to 0$ (The logarithm grows more slowly than every positive real power).

[F5]

The integral logarithm is strictly increasing on $(0, \infty)$ and unbounded above, and equals the natural logarithm there (The integral logarithm is continuous and strictly increasing on (0,∞), The integral logarithm is unbounded above and below, The integral logarithm L is the published natural logarithm).

Proof

Given: The objects and hypotheses in the Statement.

Goal: Prove its conclusions.

1.1F1F2F3givenalgebra

For $i \neq j$ , $E A_{i j} = p$ and $E (A_{i j} - p)^{2} = p (1 - p)$ by the two Bernoulli outcomes. Hence $H_{i j}$ has mean zero, variance $p (1 - p) / μ \leq 1 / n$ and absolute value at most $1 / \sqrt{μ}$ . Its row variance sum is $(n - 1) p (1 - p) / μ \leq 1$ . The diagonal vanishes, and symmetry and independence follow from the edge coordinates. The mean matrix and centering identities follow entry by entry.

2.1F4F5step 1.1algebra∎

For any real $M$ , [F5] gives $b > 0$ with $\log b > M$ ; monotonicity then gives $\log n \geq \log b > M$ for every integer $n \geq b$ . Thus $\log n \to \infty$ and $μ = γ \log n \to \infty$ . By [F4] with $a = 1$ and $a = 1 / 5$ , $p = γ \log n / n \to 0$ and $μ / n^{1 / 5} \to 0$ . Consequently, for all sufficiently large integers $n$ , $μ \geq 1$ , $0 < p < 1$ , and $μ \leq n^{1 / 5}$ , giving $1 \leq q = \sqrt{μ} \leq n^{1 / 10}$ .

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.