A Sauer-Shelah-Perles lemma for lattices
From MaRDI portal
Publication:2209889
DOI10.37236/9273zbMath1484.06018arXiv1807.04957OpenAlexW3097747961WikidataQ124791920 ScholiaQ124791920MaRDI QIDQ2209889
Stijn Cambie, Zeev Dvir, Yuval Filmus, Bogdan Chornomaz, Shay Moran
Publication date: 5 November 2020
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1807.04957
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Shattering-extremal set systems of VC dimension at most 2
- Two refinements of the bound of Sauer, Perles and Shelah, and of Vapnik and Chervonenkis
- On the density of sets of vectors
- General forbidden configuration theorems
- \(\epsilon\)-nets and simplex range queries
- A circuit set characterization of antimatroids
- Lopsided sets and orthant-intersection by convex sets
- Almost tight bounds for \(\epsilon\)-nets
- Existence of submatrices with all possible columns
- Coordinate density of sets of vectors
- A graph-theoretic generalization of the Sauer-Shelah lemma
- On randomized one-round communication complexity
- Shattering news
- Well-known bound for the VC-dimension made easy
- Convex geometries are extremal for the generalized Sauer-Shelah bound
- Teaching dimension, VC dimension, and critical sets in Latin squares
- Quasi-optimal range searching in spaces of finite VC-dimension
- On the trace of finite sets
- On the number of sets in a null t-design
- A generalization of Sauer's lemma
- Defect Sauer results
- Shattering-extremal set systems of small VC-dimension
- Combinatorics of lopsided sets
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- Integer cells in convex sets
- The structure of relatively complemented lattices
- Learnability and the Vapnik-Chervonenkis dimension
- Shattered Sets and the Hilbert Function
- Sign rank versus Vapnik-Chervonenkis dimension
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
This page was built for publication: A Sauer-Shelah-Perles lemma for lattices
