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.

Extremal-degree asymptotics near connectivity

PDF p. 31: Section 6, citation to [9, Exercise 3.4]; PDF p. 32: Section 6, equation (6.3) and preceding degree asymptotics

Statement

Fix $γ > 1$ and put $p = γ \log n / n$ . For all sufficiently large $n$ , let $G (n, p)$ be the random simple graph on $[n] = {1, \dots, n}$ in which each possible edge is present independently with probability $p$ . The degree $d (v)$ is the number of edges incident to $v$ ; write $d_{\min} = \min_{v} d (v)$ and $d_{\max} = \max_{v} d (v)$ . Let $h (c) = (1 + c) \log (1 + c) - c$ for $c > - 1$ , and let $c^{-} (γ) \in (- 1, 0)$ and $c^{+} (γ) > 0$ be the unique roots of $γ h (c) = 1$ in their respective intervals. Then, with high probability,

$d_{\min} = (1 + o (1)) (1 + c^{-} (γ)) p n, d_{\max} = (1 + o (1)) (1 + c^{+} (γ)) p n .$

Here the $o (1)$ terms can be taken as deterministic error bounds tending to zero: there is a deterministic sequence $δ_{n} ↓ 0$ such that the absolute relative errors in both displayed formulas are at most $δ_{n}$ with probability tending to one. High probability means that this probability tends to one as $n \to \infty$ .

Statement references

Erdős–Rényi random graph and high probability

Adjacency, degrees, graph Laplacian, and spectral notation

Degree large-deviation rate function and roots

Asymptotic quantifiers and uniform parameter ranges

Facts & Assumptions

[F1]

For the stated graph sequence, if $I (a) = a \log a - a + 1$ for $a > 0$ and $a_{-} \in (0, 1)$ and $a_{+} > 1$ are the unique solutions of $γ I (a) = 1$ , then $d_{\min} / (p n) \to a_{-}$ and $d_{\max} / (p n) \to a_{+}$ jointly in probability: for each $ε > 0$ , the probability that either normalized degree differs from its limit by more than $ε$ tends to zero (Extremal degrees at a fixed logarithmic mean).

[F2]

For $γ > 1$ , the roots $c^{-} (γ) \in (- 1, 0)$ and $c^{+} (γ) > 0$ exist uniquely as stated (Degree large-deviation rate function and roots).

[F3]

High probability and deterministic $o (1)$ are limits along the integer index $n$ (Erdős–Rényi random graph and high probability, Asymptotic quantifiers and uniform parameter ranges).

Proof

Given: Fixed $γ > 1$ and the graph sequence in the Statement.

Goal: Establish both displayed relative asymptotics simultaneously with high probability.

1.1F1F2algebra

For every $c > - 1$ , direct substitution gives $h (c) = I (1 + c)$ . The change of variable $a = 1 + c$ maps $(- 1, 0)$ to $(0, 1)$ and $(0, \infty)$ to $(1, \infty)$ . By the root uniqueness in [F1] and [F2], $a_{-} = 1 + c^{-} (γ)$ and $a_{+} = 1 + c^{+} (γ)$ ; both are positive. Consequently [F1] gives joint convergence in probability of $d_{\min} / (a_{-} p n)$ and $d_{\max} / (a_{+} p n)$ to $1$ .

2.1F3step 1.1choose∎

Let $R_{n}$ be the maximum of the two absolute relative errors in step 1.1. For each positive integer $k$ , convergence in probability gives an integer $N_{k}$ such that $P (R_{n} > 1 / k) < 1 / k$ for all $n \geq N_{k}$ . Choose the $N_{k}$ strictly increasing, and, for $N_{k} \leq n < N_{k + 1}$ , set $δ_{n} = 1 / k$ ; choose any positive initial values for the finitely many earlier indices. Then $δ_{n} \to 0$ and $P (R_{n} > δ_{n}) \to 0$ . By [F3], both displayed estimates therefore hold simultaneously with high probability, with deterministic relative error bound $δ_{n}$ .

Source notes

The article states these asymptotics in Section 6 and attributes them to Bollobás [9, Exercise 3.4]. The argument above uses the separately supplied degree proposition; the article citation records attribution only.

Depends on

Used by · 1

Failure of symmetric Laplacian control near 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.

Sources

Expander graphs are globally synchronizing · PDF pp. 31–32, Section 6, degree asymptotics and equation (6.3)