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.

A rare logarithmic degree occurs with probability of its first-moment order

Statement

Fix $γ > 1$ and $a > 0$ with $γ I (a) = 1$ , where $I (a) = a \log a - a + 1$ . Let $p = γ \log n / n$ and $k = a γ \log n + O (1)$ be integer. For the loop-free independent-edge graph $G (n, p)$ , let $Z$ be the number of vertices of degree exactly $k$ , and put $m_{n} = E Z$ . Then $m_{n} = Θ ((\log n)^{- 1 / 2})$ , and for all sufficiently large $n$ , $\frac{1}{2} m_{n} \leq P (Z > 0) \leq m_{n} .$ No independence of the vertex degrees is assumed.

Facts & Assumptions

[F1]

Each degree is $Bin (n - 1, p)$ ; distinct degrees decompose as $d (u) = A_{u v} + R_{u}$ , $d (v) = A_{u v} + R_{v}$ , with three independent variables, $A_{u v}$ Bernoulli $(p)$ and $R_{u}, R_{v}$ binomial $(n - 2, p)$ (Single-vertex degree laws and the shared-edge dependence).

[F2]

For fixed $a, γ$ and bounded rounding, the binomial atom is $Θ (n^{- γ I (a)} / \sqrt{\log n})$ (Exact logarithmic binomial masses at bounded distance from an entropy root); adjacent binomial masses follow from their exact formula (The Binomial count has its usual probability mass function).

[F3]

On the finite graph probability space, expectation is the sum of each value times its outcome probability, and distributes over finite sums (Expectation of a real random variable on a finite probability space).

Proof

Given: The parameters and count $Z$ in the Statement.

Goal: Compare the probability of an occurrence with $m_{n}$ .

1.1F1F2F3givenalgebra

Write $q = P (d (v) = k)$ . By [F1] and [F2], $m_{n} = n q = Θ ((\log n)^{- 1 / 2}) \to 0$ . Put $b_{i} = P (R_{u} = i)$ and $r = b_{k - 1} / b_{k} = k (1 - p) / ((n - 1 - k) p)$ , which tends to $a$ . The shared-edge decomposition gives $q = b_{k} (1 - p + p r)$ and $P (d (u) = k, d (v) = k) = b_{k}^{2} (1 - p + p r^{2})$ . Their ratio is $1 + p (1 - p) (r - 1)^{2} / (1 - p + p r)^{2} \to 1$ and is at most $2$ eventually.

2.1F3step 1.1algebra∎

For every nonnegative integer $z$ , $z - z (z - 1) / 2 \leq 1_{{z > 0}} \leq z$ : check $z = 0, 1, 2$ directly and note the left expression is nonpositive for $z \geq 3$ . Take expectations using [F3]. Step 1.1 bounds the ordered-pair sum $E [Z (Z - 1)]$ by $2 n (n - 1) q^{2} \leq 2 m_{n}^{2}$ . Therefore $m_{n} - m_{n}^{2} \leq P (Z > 0) \leq m_{n}$ . Since $m_{n} \leq 1 / 2$ eventually, the asserted lower bound follows.

Depends on

Used by · 1

The exact unshifted expansion event cannot have polynomial failure decay

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.