×

A generalization of Sauer’s lemma. (English) Zbl 0831.60011

The authors generalize N. Sauer’s lemma [ibid. 13, 145-147 (1972; Zbl 0248.05005)] to multivalued functions, proving tight bounds on the cardinality of subsets of \(\prod^m_{i= 1} \{0,\dots, N_i\}\) which avoid certain patterns. In addition, the authors give an application of this result, bounding the uniform rate of convergence of empirical estimates of the expectations of a set of random variables to their true expectations.

MSC:

60C05 Combinatorial probability
60F05 Central limit and other weak theorems
05A99 Enumerative combinatorics

Citations:

Zbl 0248.05005
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Aldred, R.E.L; Anstee, R.P, On the density of sets of divisors, (1991), unpublished manuscript · Zbl 0820.05056
[2] Alon, N, On the density of sets of vectors, Discrete math., 24, 177-184, (1983)
[3] Anstee, R.P, General forbidden configuration theorems, J. combin. theory ser. A, 40, 108-124, (1985) · Zbl 0619.05015
[4] Anstee, R.P, A forbidden configuration theorem of Alon, J. combin. theory ser. A, 47, 16-27, (1988) · Zbl 0672.05003
[5] Anstee, R.P, On a conjecture concerning forbidden submatrices, (1991), unpublished manuscript · Zbl 0985.05014
[6] Anstee, R.P; Furedi, Z, Forbidden submatrices, Discrete math., 62, 225-243, (1986) · Zbl 0646.05009
[7] Blumer, A; Ehrenfeucht, A; Haussler, D; Warmuth, M.K, Learnability and the vapnik-chervonenkis dimension, J. assoc. comput. Mach., 36, No. 4, 929-965, (1989) · Zbl 0697.68079
[8] Bondy, J.A, Induced subsets, J. combin. theory ser. B, 12, 201-202, (1972) · Zbl 0211.56901
[9] Dudley, R.M, A course on empirical processes, Lecture notes in math., 1097, 2-142, (1984) · Zbl 0554.60029
[10] Frankl, P, On the trace of finite sets, J. combin. theory ser. A, 34, 41-45, (1983) · Zbl 0505.05001
[11] Frankl, P; Furedi, Z; Pach, J, Bounding one-way differences, European J. combin., 3, 341-347, (1987) · Zbl 0663.05003
[12] Haussler, D, Generalizing the PAC model: sample size bounds from metric dimension-based uniform convergence results, () · Zbl 0747.68045
[13] Karpovsky, M.G; Milman, V.D, Coordinate density of sets of vectors, Discrete math., 24, 177-184, (1978) · Zbl 0401.05015
[14] Natarajan, B.K, On learning sets and functions, Machine learning, 4, 67-97, (1989)
[15] Pollard, D, Convergence of stochastic processes, (1984), Springer-Verlag New York/Berlin · Zbl 0544.60045
[16] Pollard, D, (), NSF-CBMS Regional Conference Series in Probability and Statistics
[17] Sauer, N, On the density of families of sets, J. combin. theory ser. A, 13, 145-147, (1972) · Zbl 0248.05005
[18] Shawe-Taylor, J; Anthony, M; Biggs, R.L, Bounding sample size with the vapnik-chervonenkis dimension, () · Zbl 0784.68070
[19] Steele, J.M, Existence of submatrices with all possible columns, J. combin. theory ser. A, 24, 84-88, (1978) · Zbl 0373.05004
[20] Tomasia, P, Dart calculus of induced subsets, Discrete math., 34, 195-198, (1981) · Zbl 0475.05002
[21] Valiant, L.G, A theory of the learnable, Comm. ACM, 27, No. 11, 1134-1142, (1984) · Zbl 0587.68077
[22] Vapnik, V.N, Estimation of dependencies based on empirical data, (1982), Springer-Verlag New York/Berlin
[23] Vapnik, V.N, Inductive principles of the search for empirical dependences (methods based on weak convergence of probability measures), () · Zbl 0746.68075
[24] Vapnik, V.N; Chervonenkis, A.Y, On the uniform convergence of relative frequencies of events to their probabilities, Theory probab. appl., 16, No. 2, 264-280, (1971) · Zbl 0247.60005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.