RemarkRemark: AI-adaptedProof: 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.

Chernoff degree concentration used in Section 6

PDF p. 31: Equation (6.2) and surrounding prose

Statement

Let $0 < ε \leq 1$ , $n \geq 12 / ε$ , and $p = γ \log n / n \in [0, 1]$ . In the simple Erdős–Rényi graph $G (n, p)$ , write $d (v)$ for the number of edges incident to vertex $v$ . Then, for any fixed vertex $v_{1}$ , $P (\exists v : ∣ d (v) - p n ∣ \geq ε p n) \leq n P (∣ d (v_{1}) - p n ∣ \geq ε p n) \leq 2 n \exp (- ε^{2} p n / 3) = 2 n^{1 - ε^{2} γ / 3} .$

Consequently, for each fixed $0 < ε \leq 1$ and each fixed $γ_{0} > 3 / ε^{2}$ , the probability on the left tends to zero uniformly for $γ \geq γ_{0}$ subject to $p \leq 1$ . If instead $γ = γ (n) \to \infty$ and $p \leq 1$ , there is a deterministic sequence $ε_{n} \to 0$ such that, with high probability, every degree lies between $(1 - ε_{n}) p n$ and $(1 + ε_{n}) p n$ .

Here “with high probability” means that the event probability tends to one as $n \to \infty$ . The parameters $c^{-}$ and $c^{+}$ are the lower and upper centered-Laplacian parameters in the two-sided $(n, d^{*}, α, c^{-}, c^{+})$ -expander definition, with reference degree $d^{*} = p n$ . In the article’s expander application, these bounds provide the degree-control part of the assertion that $∣ c^{\pm} ∣ = o (1)$ ; the separate centered-adjacency bound and the degree-to-expander implication are also needed for that spectral assertion.

Statement references

Two-sided spectral expander — Definition 1.9

Degree control implies two-sided expansion — Proposition 3.2

Facts & Assumptions

[F1]

In $G (n, p)$ the indicators of distinct possible edges are independent Bernoulli $(p)$ variables, and each degree is their sum over the $n - 1$ possible incident edges. In particular, all vertices have the same degree distribution. (Erdős–Rényi random graph and high probability, Adjacency, degrees, graph Laplacian, and spectral notation, Single-vertex degree laws and the shared-edge dependence)

[F2]

For a sum of independent Bernoulli variables with mean $μ$ , its upper and lower tail probabilities at relative displacement $δ \in [0, 1]$ are at most $\exp (- μ δ^{2} / 3)$ and $\exp (- μ δ^{2} / 2)$ , respectively. (Chernoff bound for independent bernoulli trials)

[F3]

The probability of a finite union is at most the sum of the probabilities; the events need not be independent. (The finite union bound)

[F4]

High probability and $o (1)$ mean convergence of the relevant deterministic probability or error sequence to one or zero, respectively. (Asymptotic quantifiers and uniform parameter ranges)

[F5]

The finite product of finite probability spaces assigns each outcome the product of its factor weights. These weights normalize, each coordinate has its original marginal law, and coordinate events from distinct factors are mutually independent. (The finite product of finite probability spaces, Product weights normalize, and coordinate events are mutually independent)

[F6]

The parameters $c^{-}$ and $c^{+}$ give the lower and upper centered-Laplacian bounds in the two-sided expander definition. With $d^{*} = p n$ , if $∥ A - p J ∥ \leq α p n$ and all degrees lie in $[(1 - η) p n, (1 + η) p n]$ , Proposition 3.2 applies with $c^{-} = - η - α$ and $c^{+} = η + α$ . (Two-sided spectral expander — Definition 1.9, Degree control implies two-sided expansion — Proposition 3.2)

Proof

Given: The parameters and graph in the Statement.

Goal: Establish the displayed estimate, its two asymptotic consequences, and their conditional role in two-sided expansion.

Proof technique: Apply separate upper and lower Chernoff tails, accounting for the exact mean $(n - 1) p$ , and then take a union bound.

1.1F1F2F5

If $p = 0$ , every degree and $p n$ are zero, so the displayed event has probability one and the displayed inequalities hold. Suppose henceforth that $p > 0$ . Fix a vertex $v$ . Let $(Ω_{G}, w_{G})$ be the original finite graph probability space. Form its product with ${0, 1}$ carrying weights $q (0) = 1 - p$ and $q (1) = p$ : the outcome $(G, b)$ has weight $w_{G} (G) q (b)$ . Lift the graph variables through the first coordinate and put $B (G, b) = b$ . By [F5], the graph and Bernoulli coordinate laws are unchanged, and $B$ is independent of every graph-coordinate event. For any assignment $E$ of incident-edge indicators and $b \in {0, 1}$ , $P (E \cap {B = b}) = P_{G} (E) q (b)$ ; [F1] factors $P_{G} (E)$ over the prescribed edges. Thus the $n - 1$ incident-edge indicators and $B$ are mutually independent Bernoulli $(p)$ variables. Their sum $Y = d (v) + B$ has mean $n p$ , and $d (v) \leq Y$ . Hence [F2] with relative displacement $ε$ bounds $P (d (v) \geq (1 + ε) p n)$ by $\exp (- ε^{2} p n / 3)$ , for the unchanged original degree law.

1.2F1F2algebra

The actual degree mean is $μ = (n - 1) p$ . Put $δ = (n ε - 1) / (n - 1)$ . The assumptions give $0 \leq δ \leq 1$ , and $(1 - δ) μ = (1 - ε) p n$ . By [F2], the lower-tail probability is at most $\exp (- p (n ε - 1)^{2} / (2 (n - 1)))$ . Since $n ε \geq 12$ , $(n ε - 1)^{2} / (2 (n - 1)) \geq ε^{2} n (11 / 12)^{2} / 2 \geq ε^{2} n / 3$ . The lower tail is therefore also at most $\exp (- ε^{2} p n / 3)$ .

2.1F1F3step 1.1step 1.2algebra

The event at one vertex is the union of its upper and lower deviation events. Applying [F3] first to those two events and then to the $n$ vertex events, and using their identical distributions from [F1], proves the two inequalities. Substitution of $p n = γ \log n$ gives the displayed power of $n$ . No independence between degrees is used.

3.1F4step 2.1algebra

For fixed $ε$ and $γ \geq γ_{0} > 3 / ε^{2}$ , the last bound is at most $2 n^{1 - ε^{2} γ_{0} / 3}$ , which tends to zero independently of $γ$ . If $γ \to \infty$ , choose $ε_{n} = \max {12 / n, γ^{- 1 / 4}}$ . Eventually $0 < ε_{n} \leq 1$ , $n \geq 12 / ε_{n}$ , and $γ ε_{n}^{2} \geq \sqrt{γ} \to \infty$ . The same displayed estimate then tends to zero, while $ε_{n} \to 0$ . Its complementary event gives the asserted simultaneous degree bounds with high probability.

4.1F4F6step 3.1algebra∎

In the regime $γ \to \infty$ , on the simultaneous degree event from step 3.1, any separately supplied bound $∥ A - p J ∥ \leq α_{n} p n$ with deterministic $α_{n} \geq 0$ and $α_{n} \to 0$ gives, by [F6], a two-sided expander with $c^{-} = - ε_{n} - α_{n}$ and $c^{+} = ε_{n} + α_{n}$ . These satisfy $∣ c^{\pm} ∣ \to 0$ . This is a conditional implication; the degree estimate supplies no probability bound for that separate spectral event.

Source notes

Equation (6.2) and the surrounding discussion are attributed to the article cited above. The proof here uses the actual mean $(n - 1) p$ and establishes the displayed estimate in the explicitly stated sufficiently-large- $n$ range. The degree bounds alone do not assert a centered-adjacency spectral estimate.

Depends on

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.

Sources

Expander graphs are globally synchronizing · PDF p. 31, equation (6.2) and surrounding paragraph