A Sauer-Shelah-Perles Lemma for Sumsets

Abstract

We show that any family of subsets $A\subseteq 2^{[n]}$ satisfies $|A|\le O\left(n^{\lceil d/2\rceil }\right)$, where $d$ is the VC dimension of $\{S△T|S,T\in A\}$, and $△$ is the symmetric difference operator. We also observe that replacing $△$ by either $\cup$ or $\cap$ fails to satisfy an analogous statement. Our proof is based on the polynomial method; specifically, on an argument due to [Croot, Lev, Pach '17].

6 pages, fixed a few typos