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.

Uniform degree slack and the vanishing synchrony condition

Statement

Fix $0 < ε < 1$ , $g > 12 / ε^{2}$ , and $K > 0$ . Let $n \geq 2$ be an integer tending to infinity, $0 < p \leq 1$ , and $G \sim G (n, p)$ on $[n] = {1, \dots, n}$ . Write $d_{\min} = \min_{v \in [n]} \deg_{G} (v)$ and $d_{\max} = \max_{v \in [n]} \deg_{G} (v)$ . Set $μ = n p \geq g \log n$ and $α = K / \sqrt{μ}$ . Uniformly over these $p$ , with probability tending to one, $(1 - ε + α) μ \leq d_{\min} \leq d_{\max} \leq (1 + ε - α) μ .$ For all sufficiently large $n$ , uniformly in this range, $μ > 0$ , $0 < α \leq 1 / 5$ , and $\frac{32 α (1 + 7 ε)}{(1 - ε)^{2}} \log ⁣ (\frac{1 + ε + α}{2 α}) < 1.$

Facts & Assumptions

[F1]

The uniform degree bound centered at $n p$ is Chernoff bounds with the exact degree mean.

[F2]

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

[F3]

The independent-edge random graph law is The Erdős-Rényi finite random graph G(n,p). Vertex degree, minimum degree and maximum degree are as in Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree.

Proof

Given: The objects and hypotheses in the Statement.

Goal: Prove all stated conclusions.

1.1F1F2F3givenalgebra

For the graph and degrees in [F3], use [F1] with deviation $ε / 2$ , since $g > 3 / (ε / 2)^{2}$ . Except on an event tending uniformly to zero, all degrees are between $(1 - ε / 2) μ$ and $(1 + ε / 2) μ$ . By [F2], $\log$ is increasing and unbounded above, hence $\log n \to \infty$ . Thus $α \leq K / \sqrt{g \log n} \to 0$ uniformly, so eventually $α \leq ε / 2$ and $α \leq 1 / 5$ . The claimed bounds follow by inclusion of these intervals. Positivity of $μ$ and $α$ is immediate for these $n$ .

2.1F2step 1.1algebra∎

Put $C_{0} = (1 + ε + 1 / 5) / 2 > 1 / 5$ . For $α \leq 1 / 5$ , the logarithm in the Statement is positive and at most $\log (C_{0} / α)$ . For $x \geq 1$ , [F2] gives $\log x = \int_{1}^{x} d t / t \leq \int_{1}^{x} d t / \sqrt{t} \leq 2 \sqrt{x}$ . Therefore the left side is at most $64 (1 + 7 ε) (1 - ε)^{- 2} \sqrt{C_{0} α}$ , tending uniformly to zero by step 1.1. It is eventually less than one as required.

Depends on

Used by · 1

Synchronization for sufficiently large logarithmic density constants

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.