CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck 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.

For $d \geq 1$ a family on $[n]$ of VC dimension at most $d$ has at most $(n + 1)^{d}$ members

Statement

Let $d \geq 1$ . If $F \subseteq P ([n])$ has VC dimension at most $d$ , then

$∣ F ∣ \leq (n + 1)^{d} .$

Facts & Assumptions

Given: a family $F \subseteq P ([n])$ with $VC (F) \leq d$ and $d \geq 1$ .

[L1]

Sauer-Shelah gives $∣ F ∣ \leq \sum_{i = 0}^{d} (\binom{n}{i})$ (Sauer–Shelah: a family on $[n]$ of VC dimension at most $d$ has at most $\sum_{i = 0}^{d} (\binom{n}{i})$ members).

[F1]

For $0 \leq i \leq n$ , increasing enumeration injects the $i$ -element subsets of $n$ into the words of length $i$ over $n$ , so $(\binom{n}{i}) \leq n^{i}$ ; for $i > n$ , $(\binom{n}{i}) = 0$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ , The set $A^{B}$ of functions $B \to A$ between finite sets is finite, with $∣ A^{B} ∣ = ∣ A ∣^{∣ B ∣}$ ).

[F2]

In $R$ , the binomial theorem gives $(n + 1)^{d} = \sum_{j = 0}^{d} ι (\binom{d}{j}) n^{j}$ (The binomial theorem in $R$ : $(x + y)^{n} = \sum_{k < n + 1} ι ⁣ (\binom{n}{k}) x^{k} y^{n - k}$ ), and for $0 \leq j \leq d$ the coefficient $ι (\binom{d}{j})$ is at least $1$ because the initial segment $j \subseteq d$ is one $j$ -element subset (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

Proof

technique · direct

1.1L1

By [L1], it suffices to bound the sum $\sum_{i = 0}^{d} (\binom{n}{i})$ .

2.1F1step 1.1

Each summand satisfies $(\binom{n}{i}) \leq n^{i}$ : use the injection in [F1] for $i \leq n$ , and its zero clause for $i > n$ . Hence $\sum_{i = 0}^{d} (\binom{n}{i}) \leq \sum_{i = 0}^{d} n^{i}$ .

3.1F2step 2.1∎

By [F2], viewed in $R$ every summand $n^{i}$ appears in the expansion of $(n + 1)^{d}$ with coefficient at least $1$ , so $\sum_{i = 0}^{d} n^{i} \leq (n + 1)^{d}$ . Since both sides are natural numbers, the same inequality holds in the present setting. Combining with step 2.1 proves the claim.

Remarks

The hypothesis $d \geq 1$ matters only to avoid the trivial constant case. The companion page's false statement replaces $(n + 1)^{d}$ by $n^{d}$ , which already fails at $n = 1$ , $d = 1$ .

Depends on

Used by

FALSE: a family on [n] of VC dimension at most d has at most nᵈ members False statement

Dependency tree · two levels

43 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

L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics, §7.4 (standard reference, not scraped)

For d≥1d≥1 a family on [n][n] of VC dimension at most dd has at most (n+1)d(n+1)d members