LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-09

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.

Qid fixed size density selection

Statement

Let $A, B$ be finite vertex sets and $1 \leq m \leq N = ∣ A ∣$ an integer. Some $m$ -subset $C \subseteq A$ satisfies $e_{G} (C, B) \leq m e_{G} (A, B) / N$ . Independently, if $2 \leq m \leq N$ , some $m$ -subset $C \subseteq A$ satisfies $e (G [C]) / (\binom{m}{2}) \leq e (G [A]) / (\binom{N}{2})$ . For $m = 1$ the internal edge count is zero. Applying the internal assertion to $\overline{G}$ gives the analogous upper-density selection. The cross-edge and internal choices need not be the same subset. Cross edges are counted as ordered adjacency pairs, so $A$ and $B$ may overlap.

Facts & Assumptions

Given: Finite $A, B$ , $N = ∣ A ∣$ , and an integer $1 \leq m \leq N$ .

[F1]

$(\binom{n}{k}) \cdot k! \cdot (n - k)! = n!$ . ( $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ ).

[F2]

$\sum_{x \in X} ∣ R_{x} ∣ = ∣ R ∣ = \sum_{y \in Y} ∣ R^{y} ∣$ . (Double counting: $\sum_{x \in X} ∣ R_{x} ∣ = ∣ R ∣ = \sum_{y \in Y} ∣ R^{y} ∣$ for a relation between finite sets).

[F3]

In a finite nonempty family of incidence rows, at least one row has size at most the average row size. (If $X$ is nonempty, some row fibre is at least the average size and some row fibre is at most the average size).

Proof

1.1

The family $C$ of $m$ -subsets of $A$ is finite and nonempty: enumerate $A$ and take its first $m$ members. Its size is $(\binom{N}{m}) > 0$ . Each ordered adjacency pair $(a, b) \in A \times B$ is counted in $e_{G} (C, B)$ precisely when $a \in C$ , and hence belongs to precisely $(\binom{N - 1}{m - 1})$ members. Double counting incidences $(C, edge)$ by [F2] and dividing by $(\binom{N}{m})$ gives average cross count $e_{G} (A, B) (\binom{N - 1}{m - 1}) / (\binom{N}{m}) = m e_{G} (A, B) / N$ , where the factorial identity [F1] gives the last ratio.

F1F2

2.1

The averaging principle [F3] applied to this incidence relation yields a member with cross count no greater than the average. This remains true if $B$ or the edge set is empty: every cross count is zero.

F3step 1.1

2.2

For $m \geq 2$ , an internal edge is in $(\binom{N - 2}{m - 2})$ members of $C$ . Repeating the incidence count [F2], its average internal count is $e (G [A]) (\binom{N - 2}{m - 2}) / (\binom{N}{m}) = e (G [A]) m (m - 1) / (N (N - 1))$ by [F1]. A member no greater than this average exists by [F3]; division by $(\binom{m}{2}) > 0$ gives the assertion.

F1F2F3step 1.1

3.1

If $m = 1$ , choose any vertex of the nonempty $A$ ; its induced graph has zero edges. For $m = N$ , the only choice is $C = A$ and the bounds are equalities. In the complement the same count gives $e (\overline{G} [C]) \leq e (\overline{G} [A]) (\binom{m}{2}) / (\binom{N}{2})$ , equivalently an internal density at least that of $G [A]$ when $m \geq 2$ .

step 2.1step 2.2algebra∎

Source notes

Proof/convention locator: Bucic, Nguyen, Scott and Seymour, Induced subgraph density I, 4.3 proof (1); 5.2 proof (1).

Depends on

Used by

Dependency tree · two levels

35 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

Bucic, Nguyen, Scott and Seymour, Induced subgraph density I (standard reference, not scraped)