A graph-theoretic generalization of the Sauer-Shelah lemma

DOI10.1016/S0166-218X(98)00012-2zbMath0918.05066WikidataQ59538613 ScholiaQ59538613MaRDI QIDQ1265742

Nicolò Cesa-Bianchi, David Haussler

Publication date: 27 September 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

metric spacepacking numbersSauer-Shelah lemmaVapnik-Chervaenkis dimension

Mathematics Subject Classification ID

Metric spaces, metrizability (54E35) Enumeration in graph theory (05C30)

Related Items (4)

A Sauer-Shelah-Perles lemma for lattices ⋮ Theory of Classification: a Survey of Some Recent Advances ⋮ On density of subgraphs of halved cubes ⋮ Integer cells in convex sets

Cites Work

• Unnamed Item
• Corrections to Central limit theorems for empirical measures
• Uniform and universal Glivenko-Cantelli classes
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Efficient distribution-free learning of probabilistic concepts
• Capacities: From information theory to extremal set theory
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• A generalization of Sauer's lemma
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Covering numbers for real-valued function classes
• Scale-sensitive dimensions, uniform convergence, and learnability
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: A graph-theoretic generalization of the Sauer-Shelah lemma