Perles–Sauer–Shelah lemma

In combinatorial mathematics and extremal set theory, the Sauer–Shelah lemma states that every family of sets with small VC dimension consists of a small number of sets. It is named after Norbert Sauer and Saharon Shelah, who published it independently of each other in 1972. The same result was also published slightly earlier and again independently, by Vladimir Vapnik and Alexey Chervonenkis, after whom the VC dimension is named. In his paper containing the lemma, Shelah gives credit also to Micha Perles, and for this reason the lemma has also been called the Perles–Sauer–Shelah lemma.

Buzaglo et al. call this lemma "one of the most fundamental results on VC-dimension", and it has applications in many areas. Sauer's motivation was in the combinatorics of set systems, while Shelah's was in model theory and that of Vapnik and Chervonenkis was in statistics. It has also been applied in discrete geometry and graph theory.

If ${\displaystyle \textstyle {\mathcal {F}}=\{S_{1},S_{2},\dots \}}$ is a family of sets, and ${\displaystyle T}$ is another set, then ${\displaystyle T}$ is said to be shattered by ${\displaystyle {\mathcal {F}}}$ if every subset of ${\displaystyle T}$ (including the empty set and ${\displaystyle T}$ itself) can be obtained as an intersection ${\displaystyle T\cap S_{i}}$ between ${\displaystyle T}$ and a set in the family. The VC dimension of ${\displaystyle {\mathcal {F}}}$ is the largest cardinality of a set shattered by ${\displaystyle {\mathcal {F}}}$.

...
Wikipedia