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 gamma-two graph has a vertex of degree at most log n with high probability

Statement

Let $n \geq 3$ be an integer, let $L = \log n$ (the natural logarithm), $p = 2 L / n$ , and let $G \sim G (n, p)$ on $[n]$ . Write $d (u) = \deg_{G} (u)$ and $d_{\min} = δ (G) = \min_{u \in [n]} d (u)$ . For all sufficiently large such $n$ , $P (d_{\min} > ⌊ L ⌋) \leq η_{n} : = \frac{2 e^{4} L}{\sqrt{n}} + \frac{2 p}{(1 - p)^{2}}, η_{n} \to 0.$ Thus a vertex of degree at most $\log n$ occurs with probability tending to one.

Facts & Assumptions

[F1]

Set $k = ⌊ L ⌋$ and $a = P (Y \leq k)$ for $Y \sim Bin (n - 2, p)$ , a sum of $n - 2$ independent Bernoulli- $p$ variables (Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials). For all sufficiently large integers $n$ , $a \geq e^{- 4} n^{- 1 / 2} / L > 0$ (A logarithmic low-degree atom for the gamma-two graph).

[F2]

Let $X$ count the vertices of degree at most $k$ and set $r = P (d (1) \leq k)$ . For $n \geq 2$ , $0 < p < 1$ and $a > 0$ , the same $a, k, p$ satisfy $r \geq (1 - p) a > 0$ and $P (X = 0) \leq 1 / (n r) + 2 p / (1 - p)^{2}$ (A second-moment bound for the absence of low-degree vertices).

[F3]

For every fixed $b > 0$ , $\log n / n^{b} \to 0$ (The logarithm grows more slowly than every positive real power).

[F4]

The model $G (n, p)$ is the finite simple graph on $[n]$ whose distinct edge indicators are independent Bernoulli- $p$ variables, for $p \in [0, 1]$ (The Erdős-Rényi finite random graph G(n,p)).

[F5]

Vertex degree counts incident edges; on a nonempty finite vertex set, $δ (G)$ is the minimum vertex degree (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

[F6]

The integer $k = ⌊ L ⌋$ satisfies $k \leq L < k + 1$ (Integer part: for every real x there is exactly one integer m with m ≤ x < m + 1).

[F7]

In a finite probability space, $P (A^{c}) = 1 - P (A)$ , probabilities are nonnegative and at most one, and $A \subseteq B$ implies $P (A) \leq P (B)$ (Normalization, nonnegativity, monotonicity, complements, and differences in a finite probability space).

Proof

Given: The objects and hypotheses in the Statement.

Goal: Prove its conclusions.

1.1F1F2F3F4F5givenalgebra

Take $n$ sufficiently large that [F1] applies and $0 < p < 1 / 2$ ; the latter is possible because $L > 0$ for $n \geq 3$ and $p = 2 L / n \to 0$ by [F3]. Thus [F4] defines the graph model, and the hypotheses of [F2] hold for the $a, k, r, X$ fixed in [F1] and [F2]. Since $[n]$ is nonempty, [F5] gives ${X = 0} = {d_{\min} > k}$ . Moreover $n r \geq n (1 - p) a \geq e^{- 4} \sqrt{n} / (2 L)$ . Substitution in [F2] therefore proves $P (d_{\min} > k) \leq 2 e^{4} L / \sqrt{n} + 2 p / (1 - p)^{2} = η_{n}$ .

2.1F3F5F6F7step 1.1algebra∎

By [F3] with $b = 1 / 2$ and $b = 1$ , $L / \sqrt{n} \to 0$ and $p \to 0$ , so $η_{n} \to 0$ . Set $A = {d_{\min} > k}$ and let $B$ be the event that some vertex has degree at most $L$ . By [F5] and [F6], $A^{c} = {d_{\min} \leq k} \subseteq B$ . Applying [F7] and step 1.1 gives $1 \geq P (B) \geq P (A^{c}) = 1 - P (A) \geq 1 - η_{n} \to 1$ , proving the final assertion.

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.