A generalization of Sauer's lemma
type: Item
instance of: scholarly article
title: A generalization of Sauer's lemma
zbMATH Open document ID: 0831.60011
DOI: 10.1016/0097-3165(95)90001-2
author: David Haussler
author: Philip M. Long
published in: Journal of Combinatorial Theory. Series A
publication date: 1996-02-11T00:00:00Z
review text: The authors generalize \textit{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.
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 60F05
Mathematics Subject Classification ID: 05A99
zbMATH DE Number: 802356
zbMATH Keywords: Vapnik-Chervonenkis dimension
zbMATH Keywords: multivalued function
zbMATH Keywords: expectation estimate
reviewed by: Zhengyan Lin
MaRDI profile type: Publication
full work available at URL: 0097-3165(95)90001-2
OpenAlex ID: W1981207991
Wikidata QID: Q124862093
cites work: On the density of sets of divisors
cites work: Coordinate density of sets of vectors
cites work: General forbidden configuration theorems
cites work: A forbidden configuration theorem of Alon
cites work: Q4487462
cites work: Forbidden submatrices
cites work: Learnability and the Vapnik-Chervonenkis dimension
cites work: Induced subsets
cites work: Q3217346
cites work: On the trace of finite sets
cites work: Bounding one-way differences
cites work: Q4013556
cites work: Convergence of stochastic processes
cites work: Q4001821
cites work: On the density of families of sets
cites work: Bounding sample size with the Vapnik-Chervonenkis dimension
cites work: Existence of submatrices with all possible columns
cites work: ``Dart calculus'' of induced subsets
cites work: A theory of the learnable
cites work: Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
cites work: Q4013523
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
description: scientific article; zbMATH DE number 802356