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. Here, the VC dimension is the largest size ${\displaystyle k}$ of a set with the property that all of its subsets can be formed by intersecting it with a member of the family. If the family has ${\displaystyle n}$ elements in its union, then the Sauer–Shelah lemma states that its number of sets is at most proportional to ${\displaystyle n^{k}}$.

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 and the Sauer–Shelah–Perles 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.