LemmaStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-08-26

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 $c$ -sparse set has self-density at most $c$ , and a $c$ -dense set has self-density at least $1 - c - 1 / ∣ X ∣$

Statement

Let $G$ be a finite simple graph, let $c \geq 0$ , and let $X \subseteq V (G)$ be nonempty.

If $X$ is $c$ -sparse, then $d_{G} (X, X) \leq c$ .
If $X$ is $c$ -dense, then $d_{G} (X, X) \geq 1 - c - 1 / ∣ X ∣$ .

Facts & Assumptions

Given: A finite simple graph $G$ , a real $c \geq 0$ , and a nonempty set $X \subseteq V (G)$ .

[L1]

A set is $c$ -sparse exactly when every vertex of the induced graph $G [X]$ has degree at most $c ∣ X ∣$ (A set is $c$ -sparse exactly when the maximum degree of the graph it induces is at most $c$ times its size, $c$ -sparse, $c$ -dense and $c$ -restricted vertex sets).

[L2]

The self-density is $d_{G} (X, X) = e_{G} (X, X) / ∣ X ∣^{2}$ (Edge counts and densities between nonempty vertex sets).

[L3]

The ordered edge count satisfies $e_{G} (X, X) = \sum_{x \in X} \deg_{G [X]} (x)$ (Double counting: $\sum_{x \in X} ∣ R_{x} ∣ = ∣ R ∣ = \sum_{y \in Y} ∣ R^{y} ∣$ for a relation between finite sets, The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form).

Proof

technique · direct

1.1L1L3

If $X$ is $c$ -sparse, then [L1] bounds every summand in [L3] by $c ∣ X ∣$ , so $e_{G} (X, X) \leq c ∣ X ∣^{2}$ .

2.1step 1.1L2algebra

Dividing the inequality of step 1.1 by $∣ X ∣^{2}$ and using [L2] gives $d_{G} (X, X) \leq c$ .

3.1L3L2givenalgebra∎

If $X$ is $c$ -dense, then every vertex of $G [X]$ has at most $c ∣ X ∣$ non-neighbours in $X ∖ {x}$ , so it has at least $∣ X ∣ - 1 - c ∣ X ∣$ neighbours in $X$ . Summing as in [L3] gives $e_{G} (X, X) \geq (1 - c - 1 / ∣ X ∣) ∣ X ∣^{2}$ , and [L2] turns this into $d_{G} (X, X) \geq 1 - c - 1 / ∣ X ∣$ .

Depends on

Used by

Dependency tree · two levels

21 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl, Strengthening Rödl's theorem, sec. 1 (standard reference, not scraped)

A cc-sparse set has self-density at most cc, and a cc-dense set has self-density at least 1−c−1/∣X∣1−c−1/∣X∣