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.

Exact normalized spectral threshold transfer

Statement

Let $A$ be the adjacency matrix of a labelled simple $d$ -regular graph on $n \geq 2$ vertices, with $d > 0$ , and let $J$ be the all-ones matrix. Define $ρ_{0} (A) = ∥ A - (d / n) J ∥_{o p}$ and the normalized centered norm $α (A) = ∥ A / d - J / n ∥_{o p}$ . Then $α (A) = ρ_{0} (A) / d$ .

For fixed integer $d \geq 1$ and each feasible order $n$ , choose an arbitrary probability space $(Ω_{n}, F_{n}, P_{n})$ and a map $ω \mapsto A_{n} (ω)$ into adjacency matrices of labelled simple $d$ -regular graphs on $n$ vertices. Assume that ${ω \in Ω_{n} : ρ_{0} (A_{n} (ω)) \geq t} \in F_{n}$ for every real $t$ . For every $ε > 0$ , the following are equal events:

${ω \in Ω_{n} : ρ_{0} (A_{n} (ω)) \geq 2 \sqrt{d - 1} + ε} = {ω \in Ω_{n} : α (A_{n} (ω)) \geq 2 \sqrt{d - 1} / d + ε / d} .$

For fixed integer $d \geq 3$ , convergence to zero of the unnormalized event probabilities for every fixed $ε > 0$ is equivalent to convergence to zero of $P_{n} ({ω \in Ω_{n} : α (A_{n} (ω)) \geq 2 \sqrt{d - 1} / d + δ})$ for every fixed $δ > 0$ . All limits are along feasible orders, with $d$ and the positive excess fixed before the limit. No uniformity over varying $d$ is asserted.

Statement references

Ordered eigenvalues and the centered regular norm

Asymptotic quantifiers and uniform parameter ranges

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

Probability measures and probability spaces

Facts & Assumptions

[F1]

Ordered eigenvalues and the centered regular norm identifies the centered operator norm $ρ_{0} (A)$ for the stated simple regular adjacency matrices, without a connectedness or nonbipartiteness assumption.

[F2]

Asymptotic quantifiers and uniform parameter ranges defines convergence of event probabilities along feasible regular orders with parameters fixed before the limit.

[F3]

The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖ defines the operator norm on a nonzero finite-dimensional inner product space as the maximum of $∥ T x ∥$ over unit vectors $x$ .

[F4]

Probability measures and probability spaces defines probability spaces and their measurable events. Here the spaces, graph-valued maps and measurable unnormalized threshold sets are those specified in the statement; no particular graph distribution is assumed.

Proof

Given: The adjacency matrices and positive degree in the statement, and, for the event assertions, the specified probability spaces, maps and measurable threshold sets.

Goal: Transfer exact threshold events and their fixed-degree asymptotics.

1.1F1F3givenalgebra

On the finite-dimensional vertex inner product space used for both displayed operator norms (over $R$ or $C$ , with the same choice for both), every unit vector $x$ satisfies $(A / d - J / n) x = (1 / d) (A - (d / n) J) x$ , hence $∥ (A / d - J / n) x ∥ = (1 / d) ∥ (A - (d / n) J) x ∥$ . Taking maxima over the same unit sphere using [F3] and $d > 0$ gives $α (A) = ρ_{0} (A) / d$ , with the centered norm as in [F1].

2.1F4givenstep 1.1algebra

Apply step 1.1 to $A_{n} (ω)$ for each $ω \in Ω_{n}$ . Dividing the unnormalized threshold inequality by $d > 0$ shows that $ω$ belongs to its threshold set exactly when it belongs to the displayed normalized threshold set. Thus the sets are equal. The first set is measurable by the given assumption, so the second is also an event and their $P_{n}$ probabilities agree by [F4].

3.1F2step 2.1algebra∎

When $d$ is fixed, $ε \mapsto δ = ε / d$ bijects the positive real numbers and preserves independence from $n$ . The assertions for every fixed positive excess therefore quantify over the same event families after this substitution. Their probabilities agree for every feasible $n$ by step 2.1, so their convergence assertions agree by [F2]. This proves the equivalence without asserting any estimate uniform over varying $d$ .

Depends on

Used by · 1

Friedman spectral expansion in the uniform simple model

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.