VC dimension and a union theorem for set systems

MaRDI QIDQ2315444zbMATH OpenFDO

Authors Stijn Cambie, António Girão, Ross J. Kang

Publication date 5 August 2019

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

Full work available at URL https://arxiv.org/abs/1808.02352, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i3p24

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

zbMATH Keywords

VC dimensionsymmetric differenceSauer-Shelah lemma

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: Fix positive integers $k$ and $d$. We show that, as $noinfty$, any set system $mathcalAsubset{2}^{[n]}$ for which the VC dimension of $riangl{e}_{i=1}^k{S}_{i}mid{S}_{i}inmathcalA$ is at most $d$ has size at most $$. Here $riangle$ denotes the symmetric difference operator. This is a $k$-fold generalisation of a result of Dvir and Moran, and it settles one of their questions. A key insight is that, by a compression method, the problem is equivalent to an extremal set theoretic problem on $k$-wise intersection or union that was originally due to ErdH{o}s and Frankl. We also give an example of a family $mathcalAsubset{2}^{[n]}$ such that the VC dimension of $mathcalAcapmathcalA$ and of $mathcalAcupmathcalA$ are both at most $d$, while $lvertmathcalAvert=Omega(n^d)$. This provides a negative answer to another question of Dvir and Moran.

Recommendations

• VC-saturated set systems
• Shattering and more: Extending the complete object
• VC-dimensions of random function classes
• A uniform version of a theorem by Dvir and Moran
• The VC-dimension of Sperner systems
• VC-dimension of sets of permutations
• An extremal problem with excluded subposet in the Boolean lattice
• Uniform eventown problems
• What Is the Minimal Cardinal of a Family Which Shatters All d-Subsets of a Finite Set?
• scientific article; zbMATH DE number 4173033

Cites work

• scientific article; zbMATH DE number 4029608 (Why is no real title available?)
• scientific article; zbMATH DE number 3683585 (Why is no real title available?)
• A Sauer-Shelah-Perles lemma for sumsets
• A combinatorial problem; stability and order for models and theories in infinitary languages
• Defect Sauer results
• Families of finite sets satisfying a union condition
• Intersection theorems for systems of finite sets
• Invitation to intersection problems for finite sets
• Multiply-intersecting families
• On a combinatorial conjecture of Erdös
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the density of families of sets
• On the trace of finite sets

Cited in

(13)

• VC-dimension of sets of permutations
• VC-saturated set systems
• A Sauer-Shelah-Perles lemma for sumsets
• Shattering news
• Multivalued generalizations of the Frankl-Pach theorem
• A note on the \(k\)-restriction problem
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• The VC-dimension of K-vertex D-polytopes
• A uniform version of a theorem by Dvir and Moran
• A note on VC-dimension and measure of sets of reals
• The VC-dimension of set systems defined by graphs
• Tight lower bounds on the VC-dimension of geometric set systems
• AN EQUIVALENCE RESULT FOR VC CLASSES OF SETS

This page was built for publication: VC dimension and a union theorem for set systems

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