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.

Independent cross-degrees produce a large degree at logarithmic density

Statement

Let $n, L, γ, p, M, k$ be as in the preceding logarithmic parameter lemma. In $G (n, p)$ , let $E$ be the event that some vertex in the first half has exactly $k$ neighbors in the second half. Then $P (E) \geq \frac{1}{1 + 2 \exp (- 49 L / 50)}, P (E^{c}) \leq 2 \exp (- 49 L / 50) .$ In particular the probability of a vertex with degree at least $k$ tends to one through even $n \to \infty$ .

Facts & Assumptions

[F1]

The parameters satisfy $k \leq L / 500$ , $M p / k \geq 1 / 4000$ , $0 < p < 1 / 2$ , and $\log 4000 < 9$ (Explicit parameters for the small-gamma logarithmic density).

[F2]

Each cross-degree has point probability $q \geq (M p / k)^{k} \exp (- 2 M p)$ at $k$ (A lower estimate for a binomial point probability).

[F3]

The cross-degrees from different first-half vertices are independent (Independent degrees into a fixed half of a random graph).

[F4]

The inverse identities give $\exp (L) = n$ (The natural logarithm as the inverse of the exponential function).

[F5]

The exponential addition formula converts products of exponential factors into sums of their exponents (The exponential addition formula exp(x+y)=exp(x)exp(y)).

[F6]

The exponential is positive and $\exp (- x) = 1 / \exp (x)$ (The exponential is positive and satisfies exp(-x)=1/exp(x)).

[F7]

The exponential is strictly increasing (The exponential function is strictly increasing).

[F8]

The exponential is its everywhere convergent power series (The real exponential function and the number e by a power series).

[F9]

The model $G (n, p)$ is the finite simple graph on $[n]$ whose edge indicators are mutually independent Bernoulli $(p)$ variables; its outcome space is the finite product of the edge spaces (The Erdős-Rényi finite random graph G(n,p)).

[F10]

Neighbors of a vertex are its adjacent vertices, and its degree is the cardinality of its full neighborhood (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

[F11]

An event is a subset of the finite outcome space, and its probability is the sum of its nonnegative outcome weights, whose total is one. Splitting these sums gives $P (E) = 1 - P (E^{c})$ and $P (B) \leq P (C)$ whenever $B \subseteq C$ (Finite probability spaces, outcome weights, events, and event probabilities).

Proof

Given: The objects and hypotheses in the Statement.

Goal: Prove the asserted conclusions.

1.1F1F2F4F5F7givenalgebra

Since $2 M p = n p = γ L$ , [F1] and [F2] give $q \geq \exp (- k \log 4000 - γ L) \geq \exp (- (9 / 500 + γ) L) \geq \exp (- L / 50)$ . By [F4] and [F5], $M q \geq \frac{1}{2} \exp (49 L / 50)$ .

2.1F3F6F9F11step 1.1algebra

In the finite graph probability space of [F9], let $E^{c}$ be the complement of $E$ . It has probability $(1 - q)^{M}$ by [F3]. For $0 \leq q < 1$ , $(1 - q)^{- 1} \geq 1 + q$ and induction gives $(1 + q)^{M} \geq 1 + M q$ . Thus $P (E^{c}) \leq 1 / (1 + M q)$ ; the same bound holds trivially at $q = 1$ . Step 1.1, [F6], and the complement identity in [F11] imply $P (E) \geq 1 / [1 + 2 \exp (- 49 L / 50)]$ and $P (E^{c}) \leq 2 \exp (- 49 L / 50)$ .

3.1F4F6F7F8F10F11step 2.1algebra∎

As $n$ increases without bound, $L = \log n$ increases without bound: otherwise monotonicity and $n = \exp (L)$ would bound $n$ . For $a > 0$ , the series gives $\exp (a L) \geq 1 + a L$ , so $\exp (- a L) \leq 1 / (1 + a L) \to 0$ by [F6]. Taking $a = 49 / 50$ in step 2.1 proves the claimed limiting assertion. The second-half neighbors of a vertex form a subset of its full neighborhood, so [F10] shows that $E$ is contained in the event of a vertex with total degree at least $k$ . Probability monotonicity from [F11] transfers the lower bound and limit to this degree event.

Depends on

Used by · 1

The proposed small-gamma centered-adjacency tail has the opposite limit

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.