A Sauer-Shelah-Perles lemma for lattices

DOI10.37236/9273zbMATH Open1484.06018arXiv1807.04957OpenAlexW3097747961WikidataQ124791920 ScholiaQ124791920MaRDI QIDQ2209889FDOQ2209889

Authors: Stijn Cambie, Bogdan Chornomaz, Zeev Dvir, Yuval Filmus, Shay Moran 

Publication date: 5 November 2020

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We study lattice-theoretical extensions of the celebrated Sauer-Shelah-Perles Lemma. We conjecture that a general Sauer-Shelah-Perlem Lemma holds for a lattice $L$ if and only if $L$ is relatively complemented, and prove partial results towards this conjecture.

Full work available at URL: https://arxiv.org/abs/1807.04957

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• The implication logic of \((n,k)\)-extremal lattices
• Convex geometries are extremal for the generalized Sauer-Shelah bound
• A graph-theoretic generalization of the Sauer-Shelah lemma
• A Remark on the Szarek–Talagrand Theorem
• Strong semimodular lattices and Frankl's conjecture

Mathematics Subject Classification ID

Structure theory of lattices (06B05) Extremal set theory (05D05)

Cites Work

• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Learnability and the Vapnik-Chervonenkis dimension
• \(\epsilon\)-nets and simplex range queries
• Almost tight bounds for \(\epsilon\)-nets
• Coordinate density of sets of vectors
• Shattering news
• Title not available (Why is that?)
• The structure of relatively complemented lattices
• On the density of sets of vectors
• On the trace of finite sets
• Defect Sauer results
• Title not available (Why is that?)
• On randomized one-round communication complexity
• Lopsided sets and orthant-intersection by convex sets
• Combinatorics of lopsided sets
• Title not available (Why is that?)
• Quasi-optimal range searching in spaces of finite VC-dimension
• A generalization of Sauer's lemma
• Two refinements of the bound of Sauer, Perles and Shelah, and of Vapnik and Chervonenkis
• Well-known bound for the VC-dimension made easy
• Shattering-extremal set systems of VC dimension at most 2
• General forbidden configuration theorems
• A circuit set characterization of antimatroids
• On the number of sets in a null t-design
• A graph-theoretic generalization of the Sauer-Shelah lemma
• Existence of submatrices with all possible columns
• Convex geometries are extremal for the generalized Sauer-Shelah bound
• Shattered sets and the Hilbert function
• Shattering-extremal set systems of small VC-dimension
• Teaching dimension, VC dimension, and critical sets in Latin squares
• Integer cells in convex sets
• Sign rank versus Vapnik-Chervonenkis dimension

Cited In (3)

• Inclusion matrices for rainbow subsets
• Convex geometries are extremal for the generalized Sauer-Shelah bound
• The implication logic of \((n,k)\)-extremal lattices

This page was built for publication: A Sauer-Shelah-Perles lemma for lattices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2209889)