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.[1][2] The same result was also published slightly earlier and again independently, by Vladimir Vapnik and Alexey Chervonenkis, after whom the VC dimension is named.[3] In his paper containing the lemma, Shelah gives credit also to Micha Perles,[2] and for this reason the lemma has also been called the Perles–Sauer–Shelah lemma and the Sauer–Shelah–Perles lemma.[4][5]

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

Buzaglo et al. call this lemma "one of the most fundamental results on VC-dimension",[4] 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[6] and graph theory.[7]

Definitions and statement

edit

If   is a family of sets and   is a set, then   is said to be shattered by   if every subset of   (including the empty set and   itself) can be obtained as the intersection   of   with some set   in the family. The VC dimension of   is the largest cardinality of a set shattered by  .

In terms of these definitions, the Sauer–Shelah lemma states that if   is a family of sets whose union has   elements, and if the number of sets in the family,  , obeys the inequality   then   shatters a set of size  . Equivalently, if the VC dimension of   is   then   can consist of at most   sets, as expressed using big O notation.

The bound of the lemma is tight: Let the family   be composed of all subsets of   with size less than  . Then the size of   is exactly   but it does not shatter any set of size  .[8]

The number of shattered sets

edit

A strengthening of the Sauer–Shelah lemma, due to Pajor (1985), states that every finite set family   shatters at least   sets.[9] This immediately implies the Sauer–Shelah lemma, because only   of the subsets of an  -item universe have cardinality less than  . Thus, when   there are not enough small sets to be shattered, so one of the shattered sets must have cardinality at least  .

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.[10]

Proof

edit

Pajor's variant of the Sauer–Shelah lemma may be proved by mathematical induction; the proof has variously been credited to Noga Alon[11] or to Ron Aharoni and Ron Holzman.[10]

Base
Every family of only one set shatters the empty set.
Step
Assume the lemma is true for all families of size less than   and let   be a family of two or more sets. Let   be an element that belongs to some but not all of the sets in  . Split   into two subfamilies, of the sets that contain   and the sets that do not contain  . By the induction assumption, these two subfamilies shatter two collections of sets whose sizes add to at least  . None of these shattered sets contain  , since a set that contains   cannot be shattered by a family in which all sets contain   or all sets do not contain  . Some of the shattered sets may be shattered by both subfamilies. When a set   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  . When a set   is shattered by both subfamilies, both   and   are shattered by  , so   contributes two units to the number of shattered sets of the subfamilies and of  . Therefore, the number of shattered sets of   is at least equal to the number shattered by the two subfamilies of  , which is at least  .

A different proof of the Sauer–Shelah lemma in its original form, by Péter Frankl and János Pach, is based on linear algebra and the inclusion–exclusion principle.[6][8] This proof extends to other settings such as families of vector spaces and, more generally, geometric lattices.[5]

Applications

edit

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 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  : a set   of samples, and a probability distribution on  , is said to be an  -approximation of the original distribution if the probability of each event with respect to   differs from its original probability by at most  . A set   of (unweighted) samples is said to be an  -net if every event with probability at least   includes at least one point of  . An  -approximation must also be an  -net but not necessarily vice versa.

Vapnik and Chervonenkis used the lemma to show that set systems of VC dimension   always have  -approximations of cardinality   Later authors including Haussler & Welzl (1987)[12] and Komlós, Pach & Woeginger (1992)[13] similarly showed that there always exist  -nets of cardinality  , and more precisely of cardinality at most[6]   The main idea of the proof of the existence of small  -nets is to choose a random sample   of cardinality   and a second independent random sample   of cardinality  , and to bound the probability that   is missed by some large event   by the probability that   is missed and simultaneously the intersection of   with   is larger than its median value. For any particular  , the probability that   is missed while   is larger than its median is very small, and the Sauer–Shelah lemma (applied to  ) shows that only a small number of distinct events   need to be considered, so by the union bound, with nonzero probability,   is an  -net.[6]

In turn,  -nets and  -approximations, and the likelihood that a random sample of large enough cardinality has these properties, have important applications in machine learning, in the area of probably approximately correct learning.[14] In computational geometry, they have been applied to range searching,[12] derandomization,[15] and approximation algorithms.[16][17]

Kozma & Moran (2013) use generalizations of the Sauer–Shelah lemma to prove results in graph theory such as that the number of strong orientations of a given graph is sandwiched between its numbers of connected and 2-edge-connected subgraphs.[7]

See also

edit

References

edit
  1. ^ Sauer, N. (1972), "On the density of families of sets", Journal of Combinatorial Theory, Series A, 13: 145–147, doi:10.1016/0097-3165(72)90019-2, MR 0307902.
  2. ^ a b Shelah, Saharon (1972), "A combinatorial problem; stability and order for models and theories in infinitary languages", Pacific Journal of Mathematics, 41: 247–261, doi:10.2140/pjm.1972.41.247, MR 0307903.
  3. ^ Vapnik, V. N.; Červonenkis, A. Ja. (1971), "The uniform convergence of frequencies of the appearance of events to their probabilities", Akademija Nauk SSSR, 16: 264–279, MR 0288823.
  4. ^ a b Buzaglo, Sarit; Pinchasi, Rom; Rote, Günter (2013), "Topological hypergraphs", in Pach, János (ed.), Thirty Essays on Geometric Graph Theory, Springer, pp. 71–81, doi:10.1007/978-1-4614-0110-0_6, ISBN 978-1-4614-0109-4.
  5. ^ a b Cambie, Stijn; Chornomaz, Bogdan; Dvir, Zeev; Filmus, Yuval; Moran, Shay (2020), "A Sauer–Shelah–Perles lemma for lattices", Electronic Journal of Combinatorics, 27 (4): P4.19, arXiv:1807.04957, doi:10.37236/9273.
  6. ^ a b c d Pach, János; Agarwal, Pankaj K. (1995), Combinatorial geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons Inc., p. 247, doi:10.1002/9781118033203, ISBN 0-471-58890-3, MR 1354145.
  7. ^ a b Kozma, László; Moran, Shay (2013), "Shattering, Graph Orientations, and Connectivity", Electronic Journal of Combinatorics, 20 (3), P44, arXiv:1211.1319, Bibcode:2012arXiv1211.1319K, doi:10.37236/3326, MR 3118952.
  8. ^ a b Gowers, Timothy (July 31, 2008), "Dimension arguments in combinatorics", Gowers's Weblog: Mathematics related discussions, Example 3.
  9. ^ Pajor, Alain (1985), Sous-espaces   des espaces de Banach, Travaux en Cours [Works in Progress], vol. 16, Paris: Hermann, ISBN 2-7056-6021-6, MR 0903247. As cited by Anstee, Rónyai & Sali (2002).
  10. ^ a b Anstee, R. P.; Rónyai, Lajos; Sali, Attila (2002), "Shattering news", Graphs and Combinatorics, 18 (1): 59–73, doi:10.1007/s003730200003, MR 1892434.
  11. ^ Kalai, Gil (September 28, 2008), "Extremal Combinatorics III: Some Basic Theorems", Combinatorics and More.
  12. ^ a b Haussler, David; Welzl, Emo (1987), " -nets and simplex range queries", Discrete and Computational Geometry, 2 (2): 127–151, doi:10.1007/BF02187876, MR 0884223.
  13. ^ Komlós, János; Pach, János; Woeginger, Gerhard (1992), "Almost tight bounds for  -nets", Discrete and Computational Geometry, 7 (2): 163–173, doi:10.1007/BF02187833, MR 1139078.
  14. ^ Blumer, Anselm; Ehrenfeucht, Andrzej; Haussler, David; Warmuth, Manfred K. (1989), "Learnability and the Vapnik–Chervonenkis dimension", Journal of the ACM, 36 (4): 929–965, doi:10.1145/76359.76371, MR 1072253.
  15. ^ Chazelle, B.; Friedman, J. (1990), "A deterministic view of random sampling and its use in geometry", Combinatorica, 10 (3): 229–249, doi:10.1007/BF02122778, MR 1092541.
  16. ^ Brönnimann, H.; Goodrich, M. T. (1995), "Almost optimal set covers in finite VC-dimension", Discrete and Computational Geometry, 14 (4): 463–479, doi:10.1007/BF02570718, MR 1360948.
  17. ^ Har-Peled, Sariel (2011), "On complexity, sampling, and  -nets and  -samples", Geometric approximation algorithms, Mathematical Surveys and Monographs, vol. 173, Providence, RI: American Mathematical Society, pp. 61–85, ISBN 978-0-8218-4911-8, MR 2760023.