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 logarithmic low-degree atom for the gamma-two graph

Statement

Let $L = \log n$ , $p = 2 L / n$ , and $k = ⌊ L ⌋$ . For all sufficiently large integers $n$ , if $Y \sim Bin (n - 2, p)$ , then $a_{n} : = P (Y \leq k) \geq P (Y = k) \geq e^{- 4} \frac{n^{- 1 / 2}}{L} .$ The binomial variable is a sum of $n - 2$ independent Bernoulli- $p$ variables.

Facts & Assumptions

[F1]

A binomial $(m, p)$ variable is a sum of $m$ mutually independent Bernoulli $(p)$ variables (Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials). Independent Bernoulli edge coordinates in the random-graph model give such sums (The Erdős-Rényi finite random graph G(n,p)).

[F2]

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

[F3]

The factorial $k!$ is the product $1 \cdot 2 \dots k$ (The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ).

[F4]

For $x > 0$ , the logarithm has derivative $\log^{'} (x) = 1 / x$ and integral $\log x = \int_{1}^{x} d t / t$ (The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t).

[F5]

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

[F6]

The logarithm is increasing and unbounded (The integral logarithm is unbounded above and below).

[F7]

The logarithm is inverse to the exponential (The natural logarithm as the inverse of the exponential function).

[F8]

The exponential satisfies its addition formula (The exponential addition formula exp(x+y)=exp(x)exp(y)).

[F9]

Real powers are defined by exponential and logarithm (Real powers for positive bases, with the zero-base positive-exponent convention).

[F10]

If $Y$ is a sum of $m$ independent Bernoulli $(p)$ variables, $m \in N_{0}$ and $0 < p < 1$ , then $P (Y = j) = (\binom{m}{j}) p^{j} (1 - p)^{m - j}$ for $j = 0, \dots, m$ (The Binomial count has its usual probability mass function).

[F11]

The binomial coefficient $(\binom{m}{j})$ counts the $j$ -element subsets of an $m$ -element set (The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|).

[F12]

For events $A \subseteq B$ in a probability space, $P (A) \leq P (B)$ (Basic identities for a probability measure, Statement, clause 2).

[F13]

If $a < b$ and $u, v$ are continuously differentiable on $[a, b]$ , integration by parts gives $\int_{a}^{b} u v^{'} = u (b) v (b) - u (a) v (a) - \int_{a}^{b} u^{'} v$ ; continuity of $u^{'}, v^{'}$ supplies their required integrability (If u,v are differentiable on [a,b] with u',v' integrable, then ∫ₐᵇ u v' = u(b)v(b)-u(a)v(a) - ∫ₐᵇ u'v, Statement).

Proof

Given: The objects and hypotheses in the Statement.

Goal: Prove its conclusions.

1.1F1F2F3F4F5F6F10F11F13givenalgebra

Eventually $L > 2$ , $0 < p < 1 / 2$ , and $2 \leq k < n - 2$ . On $[1, k]$ , take $u (t) = \log t$ and $v (t) = t$ . By [F4], their derivatives are $u^{'} (t) = 1 / t$ and $v^{'} (t) = 1$ , both continuous on this interval, so [F13] applies and gives $\int_{1}^{k} \log t d t = k \log k - k + 1$ . Monotonicity of the logarithm gives $\log (k!) \leq \int_{1}^{k} \log t d t + \log k = k \log k - k + 1 + \log k$ , so $k! \leq e k (k / e)^{k}$ . Counting ordered distinct selections, with each $k$ -element subset having $k!$ orderings, gives $(\binom{n - 2}{k}) \geq (n - 2 - k)^{k} / k!$ . The exact binomial atom from [F10], applied with $m = n - 2$ and $j = k$ , is therefore at least $(e k)^{- 1} [e (n - 2 - k) p / k]^{k} (1 - p)^{n - 2 - k}$ .

2.1F2F4F7F8step 1.1algebra

Put $u = (k + 2) / n$ . Eventually $u < 1 / 2$ . The integral identity gives $\log (1 - u) \geq - 2 u$ and $\log (1 - p) \geq - p / (1 - p)$ . Since $n p = 2 L$ and $k \leq L$ , step 1.1 is at least $(e L)^{- 1} \exp (k (1 + \log 2) - 2 k (k + 2) / n - 2 L / (1 - p))$ . Using $k \geq L - 1$ , this is at least $e^{- 2 - \log 2} L^{- 1} \exp ((- 1 + \log 2) L) \exp (- 2 L (L + 2) / n - 2 L p / (1 - p))$ .

3.1F4F5F9F12step 2.1algebra∎

The two nonnegative error terms in the last exponential have sum tending to zero by [F5], hence eventually at most 1. The integral for $\log 2$ gives $1 / 2 < \log 2 < 1$ . Thus $e^{- 2 - \log 2} e^{- 1} \geq e^{- 4}$ and $\exp ((- 1 + \log 2) L) \geq n^{- 1 / 2}$ . This proves the point-mass bound. Since the events satisfy ${Y = k} \subseteq {Y \leq k}$ , probability monotonicity [F12] gives $P (Y \leq k) \geq P (Y = k)$ , proving the lower-tail bound.

Depends on

Used by · 1

The gamma-two graph has a vertex of degree at most log n with high probability

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.