A generalization of Sauer's lemma

DOI10.1016/0097-3165(95)90001-2zbMath0831.60011OpenAlexW1981207991WikidataQ124862093 ScholiaQ124862093MaRDI QIDQ1899068

Philip M. Long, David Haussler

Publication date: 11 February 1996

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(95)90001-2

zbMATH Keywords

Vapnik-Chervonenkis dimensionmultivalued functionexpectation estimate

Mathematics Subject Classification ID

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

Related Items (13)

Efficient algorithms for learning functions with bounded variation ⋮ Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension ⋮ VC bounds on the cardinality of nearly orthogonal function classes ⋮ Inapproximability of Truthful Mechanisms via Generalizations of the Vapnik--Chervonenkis Dimension ⋮ A Sauer-Shelah-Perles lemma for lattices ⋮ MULTIVALUED GENERALIZATIONS OF THE FRANKL–PACH THEOREM ⋮ \(\varepsilon\)-approximations of \(k\)-label spaces ⋮ A lower bound for families of Natarajan dimension \(d\) ⋮ One-inclusion hypergraph density revisited ⋮ A graph-theoretic generalization of the Sauer-Shelah lemma ⋮ On the VC-dimension and boolean functions with long runs ⋮ On density of subgraphs of halved cubes ⋮ Integer cells in convex sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• General forbidden configuration theorems
• Forbidden submatrices
• Bounding one-way differences
• A forbidden configuration theorem of Alon
• ``Dart calculus of induced subsets
• Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
• Bounding sample size with the Vapnik-Chervonenkis dimension
• Existence of submatrices with all possible columns
• Coordinate density of sets of vectors
• On the density of sets of divisors
• On the trace of finite sets
• Induced subsets
• On the density of families of sets
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Convergence of stochastic processes

This page was built for publication: A generalization of Sauer's lemma