If , then .
The elementary estimate converts finite VC dimension into a polynomial bound on the number of sample labelings.
Articles by others on the same topic
The Sauer–Shelah lemma is a result in combinatorics and model theory that provides a bound on the size of a family of finite sets that can be shattered by a given number of points. It is named after Sigmund Sauer and Saharon Shelah, who independently discovered it.