VC dimension and a union theorem for set systems

Stijn Cambie¹ ; António Girão² ; Ross J. Kang¹

¹Radboud University Nijmegen
²University of Cambridge

The electronic journal of combinatorics, Tome 26 (2019) no. 3

Résumé

Fix positive integers $k$ and $d$. We show that, as $n\to\infty$, any set system $\mathcal{A} \subset 2^{[n]}$ for which the VC dimension of $\{ \triangle_{i=1}^k S_i \mid S_i \in \mathcal{A}\}$ is at most $d$ has size at most $(2^{d\bmod{k}}+o(1))\binom{n}{\lfloor d/k\rfloor}$. Here $\triangle$ 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 Erdős and Frankl. We also give an example of a family $\mathcal{A} \subset 2^{[n]}$ such that the VC dimension of $\mathcal{A}\cap \mathcal{A}$ and of $\mathcal{A}\cup \mathcal{A}$ are both at most $d$, while $\lvert \mathcal{A} \rvert = \Omega(n^d)$. This provides a negative answer to another question of Dvir and Moran.

Détail

DOI : 10.37236/8288

Classification : 05D05
Mots-clés : VC dimension, Sauer-Shelah lemma, symmetric difference