Two refinements of the bound of Sauer, Perles and Shelah, and of Vapnik and Chervonenkis

DOI10.1016/j.disc.2010.07.023zbMath1228.05277OpenAlexW2016554949MaRDI QIDQ712258

Balin Fleming, R. P. Ansteeand

Publication date: 28 October 2010

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

Full work available at URL: https://doi.org/10.1016/j.disc.2010.07.023

zbMATH Keywords

traceVC-dimensionforbidden configurations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal set theory (05D05)

Related Items (7)

Evidence for a forbidden configuration conjecture: One more case solved ⋮ Forbidden configurations and repeated induction ⋮ A Sauer-Shelah-Perles lemma for lattices ⋮ Linear algebra methods for Forbidden configurations ⋮ Forbidden configurations and product constructions ⋮ Forbidden Berge hypergraphs ⋮ Forbidden configurations: boundary cases

Cites Work

• Unnamed Item
• Linear algebra methods for Forbidden configurations
• Pairwise intersections and forbidden configurations
• Small forbidden configurations
• Bounded VC-dimension implies a fractional Helly theorem
• A survey of forbidden configuration results
• Small forbidden configurations. IV: The 3 rowed case
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: Two refinements of the bound of Sauer, Perles and Shelah, and of Vapnik and Chervonenkis