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.

Transfer two nonbacktracking good events to the required norm bound

Statement

Let $G = (V, E)$ be a finite simple graph on $n$ ordered vertices, with adjacency matrix $A$ . Let $J$ be the $n \times n$ all-ones matrix and $I$ the $n \times n$ identity matrix. Write $d (i)$ for the degree of vertex $i$ in this order and $d_{\max} = \max_{i} d (i)$ . Let $0 < p < 1$ , $μ = n p > 16$ , and $H = (A - p (J - I)) / \sqrt{μ}$ . All matrix norms below are Euclidean operator norms on $C^{n}$ . For a matrix $H$ , its nonbacktracking matrix $B$ is indexed by all ordered vertex pairs and has $B_{(i, j), (k, l)} = H_{k l} 1_{j = k} 1_{i \neq l}$ . Write $ρ (B) = \max {∣ z ∣ : z is an eigenvalue of B}$ . If $d_{\max} < 8 μ$ and $ρ (B) < 2$ , then $∥ A - p J ∥ < 8 \sqrt{μ}$ .

Facts & Assumptions

[F1]

The operator norm on bounded linear maps between normed spaces satisfies the triangle inequality and absolute homogeneity (The operator norm is a norm on the space of bounded linear operators). The finite-dimensional operator norm used here is the maximum over the Euclidean unit sphere (The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖).

[F2]

For a Hermitian matrix $H$ , set $r = \max_{i} (\sum_{j} ∣ H_{i j} ∣^{2})^{1 / 2}$ and $b = \max_{i j} ∣ H_{i j} ∣$ . If $r > 0$ , Theorem 2.2 gives $∥ H ∥ \leq r f (ρ (B) / r) + 7 b$ , where $f (x) = 2$ for $0 \leq x \leq 1$ and $f (x) = x + x^{- 1}$ for $x \geq 1$ .

[F3]

In an ordered finite simple graph, $A$ is symmetric with zero diagonal; row $i$ has $d (i)$ entries equal to one and $n - 1 - d (i)$ off-diagonal entries equal to zero (The adjacency matrix of a finite simple graph, Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

External input

For a matrix $H$ , its nonbacktracking matrix $B$ is indexed by ordered vertex pairs and has $B_{(i, j), (k, l)} = H_{k l} 1_{j = k} 1_{i \neq l}$ . Write $ρ (B) = \max {∣ z ∣ : z is an eigenvalue of B}$ . For a Hermitian matrix $H$ , set $r = \max_{i} (\sum_{j} ∣ H_{i j} ∣^{2})^{1 / 2}$ and $b = \max_{i j} ∣ H_{i j} ∣$ . If $r > 0$ , Theorem 2.2 gives $∥ H ∥ \leq r f (ρ (B) / r) + 7 b$ , where $f (x) = 2$ for $0 \leq x \leq 1$ and $f (x) = x + x^{- 1}$ for $x \geq 1$ .

Proof

Given: The objects and hypotheses in the Statement.

Goal: Prove its conclusions.

1.1F1givenalgebra

Since $n p > 16$ and $0 < p < 1$ , we have $n > 0$ . For any matrix $T$ on $C^{n}$ , let $M$ be its finite unit-sphere maximum from [F1]. For $x \neq 0$ , rescaling to $x / ∥ x ∥$ gives $∥ T x ∥ \leq M ∥ x ∥$ ; the same inequality holds at zero. Thus $T$ is bounded, and its unit-ball supremum equals $M$ , since it is at most $M$ and the unit ball contains the unit sphere. Consequently the triangle inequality and absolute homogeneity in [F1] apply to our finite-dimensional matrix norm. Also $∥ I x ∥ = 1$ for every unit vector, so $∥ I ∥ = 1$ .

1.2F2F3givenalgebra

Let $r, b$ be as in [F2] and put $ρ = ρ (B)$ . By [F3], $H$ is real symmetric, hence Hermitian, with zero diagonal. Its off-diagonal entries are $(1 - p) / \sqrt{μ}$ at adjacent vertices and $- p / \sqrt{μ}$ otherwise. Hence $b \leq 1 / \sqrt{μ}$ and $\sum_{j} ∣ H_{i j} ∣^{2} = [d (i) (1 - p)^{2} + (n - 1 - d (i)) p^{2}] / μ \leq d (i) / μ + p < 9$ , so $r < 3$ . For $r > 0$ , $r f (ρ / r) \leq 2 \max {r, ρ}$ : if $ρ \leq r$ it is $2 r$ , and if $ρ \geq r$ it is $ρ + r^{2} / ρ \leq 2 ρ$ . Thus [F2] and $ρ < 2$ give $∥ H ∥ < 6 + 7 / \sqrt{μ}$ . If $r = 0$ , every entry of $H$ vanishes and this bound is immediate.

2.1step 1.1step 1.2algebra∎

Since $A - p J = \sqrt{μ} H - p I$ , step 1.1 and step 1.2 give $∥ A - p J ∥ \leq \sqrt{μ} ∥ H ∥ + p ∥ I ∥ < 6 \sqrt{μ} + 7 + p < 6 \sqrt{μ} + 8 < 8 \sqrt{μ}$ , the last comparison using $μ > 16$ .

Depends on

Used by · 1

The restricted spectral estimate needed above the connectivity threshold

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

Benaych-Georges, Bordenave and Knowles, Spectral radii of sparse random matrices (19 September 2019) · PDF p. 3, Definition 2.1; p. 4, Theorem 2.2

For a Hermitian matrix $H$, set $r=\max_i(\sum_j|H_{ij}|^2)^{1/2}$ and $b=\max_{ij}|H_{ij}|$. If $r>0$, Theorem 2.2 gives $\|H\|\le r f(\rho(B)/r)+7b$, where $f(x)=2$ for $0\le x\le1$ and $f(x)=x+x^{-1}$ for $x\ge1$.

Hypotheses: Finite Hermitian H; the nonbacktracking matrix is defined by the displayed ordered-pair formula. Treat H=0 separately.

Reading limits: Checked the extracted PDF text on pp. 3–4 for Definition 2.1, the matrix norm conventions and Theorem 2.2, including its full deterministic Hermitian hypothesis. The theorem is imported; its proof and the remaining paper were not reconstructed or fully read.

Sources

Benaych-Georges, Bordenave and Knowles, Spectral radii of sparse random matrices (19 September 2019) · PDF p. 3, Definition 2.1; p. 4, Theorem 2.2