A set system \(\mathcal F\) on the finite underlying set \(X\) shatters a set \(D \subset X\) if the trace of \(\mathcal F\) on \(D\) is the power-set of \(D.\) The maximum size of a set shattered by \(\mathcal F\) is the VC-dimension of the family \(\mathcal F\). P. Frankl started to investigate maximum Sperner families having bounded VC-dimension. This paper evaluates the maximum possible VC-dimension of a Sperner family and gives an upper bound for the size of a Sperner family with this maximum VC-dimension.
Recommendations
Cites work
- Counterexample to the Frankl-Pach conjecture for uniform, dense families
- scientific article; zbMATH DE number 3972833 (Why is no real title available?)
- On disjointly representable sets
- On the density of families of sets
- On the trace of finite sets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Sperner families of bounded VC-dimension
- Traces of antichains
Cited in
(11)- Sperner families of bounded VC-dimension
- A Sauer-Shelah-Perles lemma for sumsets
- Hook removal operators on the odd Young graph
- Shattering-extremal set systems of small VC-dimension
- VC-saturated set systems
- A uniform version of a theorem by Dvir and Moran
- VC dimension and a union theorem for set systems
- The VC-dimension of K-vertex D-polytopes
- Shattering-extremal set systems of VC dimension at most 2
- THICKET DENSITY
- VC-dimension of sets of permutations
This page was built for publication: The VC-dimension of Sperner systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1296751)
