A Sauer-Shelah-Perles lemma for lattices

DOI10.37236/9273MaRDI QIDQ2209889zbMATH OpenOpenAlexWikidataFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(3)

• Convex geometries are extremal for the generalized Sauer-Shelah bound
• Inclusion matrices for rainbow subsets
• 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)