VC dimension and a union theorem for set systems

Abstract

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 $\{{△}_{i=1}^k{S}_i\mid S_i\in \mathcal{A}\}$ is at most $d$ has size at most $(2^{d\mathrm{mod}k}+o(1))\left(\genfrac{}{}{0ex}{}{n}{\lfloor d/k\rfloor }\right)$. Here $△$ 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 $|\mathcal{A}|=\Omega (n^d)$. This provides a negative answer to another question of Dvir and Moran.

arXiv comment7 pages; in v2 added references to earlier work of Frankl