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.

The original shifted roots impose a minimum degree above log n

Statement

Let $G = (V, E)$ be a finite undirected graph on $n = ∣ V ∣ \geq 2$ vertices with symmetric binary adjacency matrix $A$ , allowing self-loops and counting each loop once in its vertex's degree. Write $d (x) = \sum_{y \in V} A_{x y}$ , $D = diag (d (x))$ , $d_{\min} (G) = \min_{x \in V} d (x)$ and $d_{\max} (G) = \max_{x \in V} d (x)$ . Let $I$ and $J$ be the identity and all-ones matrices on the vertex space.

Take the admissible original parameters $γ = 2$ , $ε = 1 / 2$ , and let $c^{-} < 0 < c^{+}$ be the original shifted roots, so $2 h (c^{-} - 1 / 2) = 2 h (c^{+} + 1 / 2) = 3 / 2$ , where $h (x) = (1 + x) \log (1 + x) - x$ for $x > - 1$ . Then $- 1 / 2 < c^{-} < 0$ . Put $L = \log n$ , $d^{*} = 2 L$ , $α = 8 / \sqrt{2 L}$ and $p = 2 L / n$ , so $p n = d^{*}$ .

The degree target (6.9) for $G$ is the condition $(1 + c^{-} + α) p n \leq d_{\min} (G) \leq d_{\max} (G) \leq (1 + c^{+} - α) p n .$ For every sufficiently large $n$ , each of this degree target and the original $(n, d^{*}, α, c^{-}, c^{+})$ -expander predicate for $G$ implies $d_{\min} (G) > L$ . The latter predicate means all three inequalities $∥ A - p J ∥ \leq α d^{*}, c^{-} d^{*} I ⪯ Δ_{L}, Δ_{L} ⪯ c^{+} d^{*} I,$ where $Δ_{L} = D - A - d^{*} I + (d^{*} / n) J$ , $∥ \cdot ∥$ is the operator norm on $C^{V}$ , and $⪯$ is Hermitian quadratic-form order.

Statement references

Adjacency, degrees, graph Laplacian, and spectral notation

Shifted rate roots for quantitative expansion

Two-sided spectral expander — Definition 1.9

Degree bounds from two-sided expansion — Lemma 3.1

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

Facts & Assumptions

[F1]

The shifted-root definition requires positive logarithm arguments and the stated signs of the roots (Shifted rate roots for quantitative expansion).

[F2]

Two-sided expansion is exactly the norm inequality and the two centered-Laplacian order inequalities (Two-sided spectral expander — Definition 1.9).

[F3]

Every such expander has $d_{\min} (G) \geq (1 + c^{-}) d^{*} - d^{*} / n$ (Degree bounds from two-sided expansion — Lemma 3.1).

[F4]

The graph conventions give binary symmetric $A$ , degrees as row sums with each loop counted once, the diagonal degree matrix $D$ , and the degree extrema of the same finite nonempty graph $G$ (Adjacency, degrees, graph Laplacian, and spectral notation).

[F5]

The natural logarithm is strictly increasing on $(0, \infty)$ and satisfies $\log 1 = 0$ (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

Proof

Given: The graph, parameters and shifted roots in the Statement; in each implication assume its stated condition on $G$ .

Goal: Prove $- 1 / 2 < c^{-} < 0$ and that each condition forces $d_{\min} (G) > L$ for sufficiently large $n$ .

1.1F1F4F5givenalgebra

The graph and its degree extrema have the conventions in [F4]. Since $n \geq 2 > 1$ , [F5] gives $L = \log n > \log 1 = 0$ , so $d^{*} = 2 L > 0$ and $α = 8 / \sqrt{2 L} > 0$ . The parameter inequalities are $0 < 1 / 2 < 1$ and $1 + 1 / 2 < 2 < 1 + (1 / 2)^{- 2} = 5$ . Positivity of $1 + c^{-} - 1 / 2$ in [F1] gives $c^{-} > - 1 / 2$ , and [F1] also gives $c^{-} < 0$ . Therefore $δ = 1 + 2 c^{-} > 0$ is a fixed positive number. If the full displayed degree target holds, its lower inequality and $p n = d^{*} = 2 L$ give $d_{\min} (G) \geq (1 + c^{-} + α) 2 L = L + (δ + 2 α) L > L$ , using $L > 0$ and $α > 0$ .

2.1F2F3F4step 1.1algebra∎

If $G$ satisfies the expander predicate, [F2] gives precisely the displayed norm and order inequalities. The graph hypotheses in [F4] allow [F3] to be applied at $d^{*} = 2 L$ , giving $d_{\min} (G) \geq L + (δ - 2 / n) L > L$ whenever $n > 2 / δ$ . Together with step 1.1, this proves both implications for every sufficiently large $n$ .

Depends on

Used by · 1

Two fixed-parameter expander events have vanishing success probabilities

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.