Authors
Citation
D. Haussler et Pm. Long, A GENERALIZATION OF SAUERS LEMMA, J COMB TH A, 71(2), 1995, pp. 219-240
Citations number
24
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES A
ISSN journal
00973165
→ ACNP
Volume
71
Issue
2
Year of publication
1995
Pages
219 - 240
Database
ISI
SICI code
0097-3165(1995)71:2<219:AGOSL>2.0.ZU;2-U
Abstract
We generalize Sauer's lemma to multivalued functions, proving tight bo
unds on the cardinality of subsets of Pi(i=1)(m), {0, ..., N-m} which
avoid certain patterns. In addition, we give an application of this re
sult, bounding the uniform rate of convergence of empirical estimates
of the expectations of a set of random variables to their true expecta
tions. (C) 1995 Academic Press, Inc.