 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-2/31l/a/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

A set of points

x_{1}, \dots, x_{n}

is shattered by

H

when every one of the

2^{n}

binary label vectors is realized by some

h \in H

s (H, n) = max_{x_{1}, \dots, x_{n}} ∣ {(h (x_{1}), \dots, h (x_{n})) : h \in H} ∣,

V C (H) = sup {n : s (H, n) = 2^{n}} .

The Sauer--Shelah lemma states that if

V C (H) = D < \infty

, then

s (H, n) \leq \sum_{j = 0}^{D} (j n)

for every

n

; in particular

s (H, n) \leq (n + 1)^{D}

 New to topics? Read the docs here!