View source for Sauer–Shelah lemma

{{Short description|Notion in combinatorics}}[[File:Sauer–Shelah lemma.svg|thumb|upright=1.35|Pajor's formulation of the Sauer–Shelah lemma: for every finite family of sets (green) there is another family of equally many sets (blue outlines) such that each set in the second family is shattered by the first family]]
In [[Combinatorics|combinatorial mathematics]] and extremal set theory, the '''Sauer–Shelah lemma''' states that every [[Family of sets|family of sets]] with small [[Vapnik–Chervonenkis dimension|VC dimension]] consists of a small number of sets. It is named after Norbert Sauer and [[Biography:Saharon Shelah|Saharon Shelah]], who published it independently of each other in 1972.{{r|sauer|shelah}} The same result was also published slightly earlier and again independently, by [[Biography:Vladimir Vapnik|Vladimir Vapnik]] and [[Biography:Alexey Chervonenkis|Alexey Chervonenkis]], after whom the VC dimension is named.{{r|vc}} In his paper containing the lemma, Shelah gives credit also to Micha Perles,{{r|shelah}} and for this reason the lemma has also been called the '''Perles–Sauer–Shelah lemma''' and the '''Sauer–Shelah–Perles lemma'''.{{r|brr|ccdfm}}

Buzaglo et al. call this lemma "one of the most fundamental results on VC-dimension",{{r|brr}} and it has applications in many areas. Sauer's motivation was in the [[Combinatorics|combinatorics]] of set systems, while Shelah's was in [[Model theory|model theory]] and that of Vapnik and Chervonenkis was in [[Statistics|statistics]]. It has also been applied in [[Discrete geometry|discrete geometry]]{{r|pa95}} and [[Graph theory|graph theory]].{{r|km13}}

==Definitions and statement==
If <math> \textstyle \mathcal{F}=\{S_1,S_2,\dots\}</math> is a family of sets and <math>T</math> is a set, then <math>T</math> is said to be [[Shattered set|shattered]] by <math>\mathcal{F}</math> if every subset of <math>T</math> (including the [[Empty set|empty set]] and <math>T</math> itself) can be obtained as the intersection <math>T\cap S_i</math> of <math>T</math> with some set <math>S_i</math> in the family. The [[VC dimension]] of <math>\mathcal{F}</math> is the largest [[Cardinality|cardinality]] of a set shattered by <math>\mathcal{F}</math>.

In terms of these definitions, the Sauer–Shelah lemma states that if <math>\mathcal{F}</math> is a family of sets whose union has <math>n</math> elements, and if the number of sets in the family, <math>|\mathcal{F}|</math>, obeys the inequality
<math display=block>|\mathcal{F}| > \sum_{i=0}^{k-1} {\binom{n}{i}},</math> then <math>\mathcal{F}</math> shatters a set of size <math>k</math>. Equivalently, if the VC dimension of <math>\mathcal{F}</math> is <math>k,</math> then <math>\mathcal{F}</math> can consist of at most <math display=block> \sum_{i=0}^{k} {\binom{n}{i}} =O(n^k)</math> sets, as expressed using [[Big O notation|big O notation]].

The bound of the lemma is tight: Let the family <math>\mathcal{F}</math> be composed of all subsets of <math>\{1,2,\dots, n\}</math> with size less than <math>k</math>. Then the size of <math>\mathcal{F}</math> is exactly <math display=inline> \sum_{i=0}^{k-1} {\binom{n}{i}}</math> but it does not shatter any set of size <math>k</math>.{{r|gowers}}

==The number of shattered sets==
A strengthening of the Sauer–Shelah lemma, due to {{harvtxt|Pajor|1985}}, states that every finite set family <math>\mathcal{F}</math> shatters at least <math>|\mathcal{F}|</math> sets.{{r|pajor}} This immediately implies the Sauer–Shelah lemma, because only  <math display=inline>\sum_{i=0}^{k-1} {\tbinom{n}{i}} </math> of the subsets of an <math>n</math>-item universe have cardinality less than <math>k</math>. Thus, when <math display=block>|\mathcal{F}|>\sum_{i=0}^{k-1} {\tbinom{n}{i}},</math> there are not enough small sets to be shattered, so one of the shattered sets must have cardinality at least <math>k</math>.

For a restricted type of shattered set, called an order-shattered set, the number of shattered sets always equals the cardinality of the set family.{{r|ars02}}

==Proof==
Pajor's variant of the Sauer–Shelah lemma may be proved by [[Mathematical induction|mathematical induction]]; the proof has variously been credited to [[Biography:Noga Alon|Noga Alon]]{{r|kalai}} or to [[Biography:Ron Aharoni|Ron Aharoni]] and Ron Holzman.{{r|ars02}}

;Base: Every family of only one set shatters the empty set. 
;Step: Assume the lemma is true for all families of size less than <math>|\mathcal{F}|</math> and let <math>\mathcal{F}</math> be a family of two or more sets. Let <math>x</math> be an element that belongs to some but not all of the sets in <math>\mathcal{F}</math>. Split <math>\mathcal{F}</math> into two subfamilies, of the sets that contain <math>x</math> and the sets that do not contain <math>x</math>. By the induction assumption, these two subfamilies shatter two collections of sets whose sizes add to at least <math>|\mathcal{F}|</math>. None of these shattered sets contain <math>x</math>, since a set that contains <math>x</math> cannot be shattered by a family in which all sets contain <math>x</math> or all sets do not contain <math>x</math>. Some of the shattered sets may be shattered by both subfamilies. When a set <math>S</math> is shattered by only one of the two subfamilies, it contributes one unit both to the number of shattered sets of the subfamily and to the number of shattered sets of <math>\mathcal{F}</math>. When a set <math>S</math> is shattered by both subfamilies, both <math>S</math> and <math>S\cup\{x\}</math> are shattered by <math>\mathcal{F}</math>, so <math>S</math> contributes two units to the number of shattered sets of the subfamilies and of <math>\mathcal{F}</math>. Therefore, the number of shattered sets of <math>\mathcal{F}</math> is at least equal to the number shattered by the two subfamilies of <math>\mathcal{F}</math>, which is at least <math>|\mathcal{F}|</math>.

A different proof of the Sauer–Shelah lemma in its original form, by [[Biography:Péter Frankl|Péter Frankl]] and [[Biography:János Pach|János Pach]], is based on [[Linear algebra|linear algebra]] and the [[Inclusion–exclusion principle|inclusion–exclusion principle]].{{r|pa95|gowers}} This proof extends to other settings such as families of vector spaces and, more generally, [[Geometric lattice|geometric lattices]].{{r|ccdfm}}

==Applications==
The original application of the lemma, by Vapnik and Chervonenkis, was in showing that every probability distribution can be approximated (with respect to a family of events of a given VC dimension) by a finite set of sample points whose [[Cardinality|cardinality]] depends only on the VC dimension of the family of events. In this context, there are two important notions of approximation, both parameterized by a number <math>\varepsilon</math>: a set <math>S</math> of samples, and a probability distribution on <math>S</math>, is said to be an <math>\varepsilon</math>-approximation of the original distribution if the probability of each event with respect to <math>S</math> differs from its original probability by at most <math>\varepsilon</math>. A set <math>S</math> of (unweighted) samples is said to be an [[Ε-net (computational geometry)|<math>\varepsilon</math>-net]] if every event with probability at least <math>\varepsilon</math> includes at least one point of <math>S</math>. An <math>\varepsilon</math>-approximation must also be an <math>\varepsilon</math>-net but not necessarily vice versa.

Vapnik and Chervonenkis used the lemma to show that set systems of VC dimension <math>d</math> always have <math>\varepsilon</math>-approximations of cardinality <math display=block>O(\tfrac{d}{\varepsilon^2}\log\tfrac{d}{\varepsilon}).</math> Later authors including {{harvtxt|Haussler|Welzl|1987}}{{r|hw87}} and {{harvtxt|Komlós|Pach|Woeginger|1992}}{{r|kpw}} similarly showed that there always exist <math>\varepsilon</math>-nets of cardinality <math>O(\tfrac{d}{\varepsilon}\log\tfrac{1}{\varepsilon})</math>, and more precisely of cardinality at most{{r|pa95}} <math display=block>\tfrac{d}{\varepsilon}\ln\tfrac{1}{\varepsilon}+\tfrac{2d}{\varepsilon}\ln\ln\tfrac{1}{\varepsilon}+\tfrac{6d}{\varepsilon}.</math> The main idea of the proof of the existence of small <math>\varepsilon</math>-nets is to choose a random sample <math>x</math> of cardinality <math display=inline>O(\tfrac{d}{\varepsilon}\log\tfrac{1}{\varepsilon})</math> and a second independent random sample <math>y</math> of cardinality <math display=inline>O(\tfrac{d}{\varepsilon}\log^2\tfrac{1}{\varepsilon})</math>, and to bound the probability that <math>x</math> is missed by some large event <math>E</math> by the probability that <math>x</math> is missed and simultaneously the intersection of <math>y</math> with <math>E</math> is larger than its median value. For any particular <math>E</math>, the probability that <math>x</math> is missed while <math>y</math> is larger than its median is very small,
and the Sauer–Shelah lemma (applied to <math>x\cup y</math>) shows that only a small number of distinct events <math>E</math> need to be considered, so by the [[Boole's inequality|union bound]], with nonzero probability, <math>x</math> is an <math>\varepsilon</math>-net.{{r|pa95}}

In turn, <math>\varepsilon</math>-nets and <math>\varepsilon</math>-approximations, and the likelihood that a random sample of large enough cardinality has these properties, have important applications in [[Machine learning|machine learning]], in the area of [[Probably approximately correct learning|probably approximately correct learning]].{{r|behw}} In [[Computational geometry|computational geometry]], they have been applied to [[Range searching|range searching]],{{r|hw87}} [[Randomized algorithm#Derandomization|derandomization]],{{r|cf}} and [[Approximation algorithm|approximation algorithm]]s.{{r|bg|har-peled}}

{{harvtxt|Kozma|Moran|2013}} use generalizations of the Sauer–Shelah lemma to prove results in [[Graph theory|graph theory]] such as that the number of [[Strong orientation|strong orientation]]s of a given graph is sandwiched between its numbers of connected and [[Bridge (graph theory)#Bridgeless graphs|2-edge-connected]] subgraphs.{{r|km13}}

== See also ==
* [[Growth function]]

== References ==
{{reflist|refs=

<ref name=ars02>{{citation
 | last1 = Anstee | first1 = R. P.
 | last2 = Rónyai | first2 = Lajos
 | last3 = Sali | first3 = Attila
 | doi = 10.1007/s003730200003 | doi-access=
 | issue = 1
 | journal = Graphs and Combinatorics
 | mr = 1892434
 | pages = 59–73
 | title = Shattering news
 | volume = 18
 | year = 2002}}.</ref> 

<ref name=behw>{{citation
 | last1 = Blumer | first1 = Anselm
 | last2 = Ehrenfeucht | first2 = Andrzej
 | last4 = Warmuth | first4 = Manfred K.
 | doi = 10.1145/76359.76371
 | issue = 4
 | journal = [[Journal of the ACM]]
 | mr = 1072253
 | pages = 929–965
 | title = Learnability and the Vapnik–Chervonenkis dimension
 | volume = 36
 | year = 1989| doi-access = free
 }}.</ref>

<ref name=bg>{{citation
 | last1 = Brönnimann | first1 = H.
 | doi = 10.1007/BF02570718
 | issue = 4
 | journal = Discrete and Computational Geometry
 | mr = 1360948
 | pages = 463–479
 | title = Almost optimal set covers in finite VC-dimension
 | volume = 14
 | year = 1995| doi-access = free
 }}.</ref>

<ref name=brr>{{citation
 | last1 = Buzaglo | first1 = Sarit
 | last2 = Pinchasi | first2 = Rom
 | last3 = Rote | first3 = Günter
 | contribution = Topological hypergraphs
 | doi = 10.1007/978-1-4614-0110-0_6 | doi-access=
 | pages = 71–81
 | publisher = Springer
 | title = Thirty Essays on Geometric Graph Theory
 | year = 2013}}.</ref>

<ref name=ccdfm>{{citation
 | last1 = Cambie | first1 = Stijn
 | last2 = Chornomaz | first2 = Bogdan
 | last3 = Dvir | first3 = Zeev
 | last4 = Filmus | first4 = Yuval
 | last5 = Moran | first5 = Shay
 | title = A Sauer–Shelah–Perles lemma for lattices
 | journal = Electronic Journal of Combinatorics
 | volume = 27
 | issue = 4
 | year = 2020
 | pages = P4.19
 | doi = 10.37236/9273
 | url = https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i4p19/pdf| doi-access = free
 | arxiv = 1807.04957
 }}. </ref>

<ref name=cf>{{citation
 | last2 = Friedman | first2 = J.
 | doi = 10.1007/BF02122778 | doi-access=
 | issue = 3
 | journal = [[Combinatorica]]
 | mr = 1092541
 | pages = 229–249
 | title = A deterministic view of random sampling and its use in geometry
 | volume = 10
 | year = 1990}}.</ref>

<ref name=gowers>{{citation|title=Dimension arguments in combinatorics|at=Example 3|first=Timothy|last=Gowers|work=Gowers's Weblog: Mathematics related discussions|url=http://gowers.wordpress.com/2008/07/31/dimension-arguments-in-combinatorics/|date=July 31, 2008}}.</ref>

<ref name=har-peled>{{citation
 | contribution = On complexity, sampling, and <math>\varepsilon</math>-nets and <math>\varepsilon</math>-samples
 | isbn = 978-0-8218-4911-8
 | location = Providence, RI
 | mr = 2760023
 | pages = 61–85
 | publisher = American Mathematical Society
 | series = Mathematical Surveys and Monographs
 | title = Geometric approximation algorithms
 | volume = 173
 | year = 2011}}.</ref>

<ref name=hw87>{{citation
 | doi = 10.1007/BF02187876
 | issue = 2
 | journal = Discrete and Computational Geometry
 | mr = 884223
 | pages = 127–151
 | title = <math>\varepsilon</math>-nets and simplex range queries
 | volume = 2
 | year = 1987| doi-access = free
 }}.</ref>

<ref name=kalai>{{citation|url=http://gilkalai.wordpress.com/2008/09/28/extremal-combinatorics-iii-some-basic-theorems/|first=Gil|last=Kalai|title=Extremal Combinatorics III: Some Basic Theorems|work=Combinatorics and More|date=September 28, 2008}}.</ref>

<ref name=km13>{{citation
 | last1 = Kozma | first1 = László
 | last2 = Moran | first2 = Shay
 | arxiv = 1211.1319
 | journal = Electronic Journal of Combinatorics
 | volume = 20 | issue = 3 | at = P44
 | title = Shattering, Graph Orientations, and Connectivity
 | url = http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p44
 | year = 2013
 | bibcode = 2012arXiv1211.1319K 
 | mr = 3118952}}.</ref>

<ref name=kpw>{{citation
 | doi = 10.1007/BF02187833
 | issue = 2
 | journal = Discrete and Computational Geometry
 | mr = 1139078
 | pages = 163–173
 | title = Almost tight bounds for <math>\varepsilon</math>-nets
 | volume = 7
 | year = 1992| doi-access = free
 }}.</ref>

<ref name=pa95>{{citation
 | last1 = Pach
 | first1 = János
 | last2 = Agarwal
 | first2 = Pankaj K.
 | doi = 10.1002/9781118033203
 | isbn = 0-471-58890-3
 | location = New York
 | mr = 1354145
 | page = [https://archive.org/details/combinatorialgeo0000pach/page/247 247]
 | publisher = John Wiley & Sons Inc.
 | series = Wiley-Interscience Series in Discrete Mathematics and Optimization
 | title = Combinatorial geometry
 | year = 1995
 | url = https://archive.org/details/combinatorialgeo0000pach/page/247
 | doi-access = 
 }}.</ref>

<ref name=pajor>{{citation
 | last = Pajor | first = Alain
 | isbn = 2-7056-6021-6
 | location = Paris
 | mr = 903247
 | publisher = Hermann
 | series = Travaux en Cours [Works in Progress]
 | title = Sous-espaces <math>l^n_1</math> des espaces de Banach
 | volume = 16
 | year = 1985}}. As cited by {{harvtxt|Anstee|Rónyai|Sali|2002}}.</ref>

<ref name=sauer>{{citation
 | last = Sauer | first = N.
 | journal = Journal of Combinatorial Theory
 | mr = 0307902
 | pages = 145–147
 | series = Series A
 | title = On the density of families of sets
 | volume = 13
 | year = 1972
 | doi=10.1016/0097-3165(72)90019-2 | doi-access=}}.</ref>

<ref name=shelah>{{citation
 |last    = Shelah
 |first   = Saharon
 |journal = Pacific Journal of Mathematics
 |mr      = 0307903
 |pages   = 247–261
 |title   = A combinatorial problem; stability and order for models and theories in infinitary languages
 |url     = http://projecteuclid.org/getRecord?id=euclid.pjm/1102968432
 |archive-url = https://archive.today/20131005003706/http://projecteuclid.org/getRecord?id=euclid.pjm/1102968432
 |url-status = dead
 |archive-date = 2013-10-05
 |volume  = 41
 |year    = 1972
 |doi     = 10.2140/pjm.1972.41.247
|doi-access= free
 }}.</ref>

<ref name=vc>{{citation
 | journal = Akademija Nauk SSSR
 | mr = 0288823
 | pages = 264–279
 | title = The uniform convergence of frequencies of the appearance of events to their probabilities
 | volume = 16
 | year = 1971}}.</ref>

}}

{{DEFAULTSORT:Sauer-Shelah lemma}}
[[Category:Lemmas]]

{{Sourceattribution|Sauer–Shelah lemma}}