A Sauer-Shelah-Perles Lemma for Sumsets
This work addresses a theoretical problem in combinatorics and computational learning theory, providing a new Sauer-Shelah-Perles-type lemma for sumsets, which is incremental as it extends known methods to a specific operator.
The paper tackles the problem of bounding the size of a family of subsets based on the VC dimension of its symmetric differences, proving that any family A satisfies |A| ≤ O(n^⌈d/2⌉) where d is the VC dimension of {S△T | S,T∈A}. The result shows that this bound holds for symmetric differences but fails for unions or intersections.
We show that any family of subsets $A\subseteq 2^{[n]}$ satisfies $\lvert A\rvert \leq O\bigl(n^{\lceil{d}/{2}\rceil}\bigr)$, where $d$ is the VC dimension of $\{S\triangle T \,\vert\, S,T\in A\}$, and $\triangle$ is the symmetric difference operator. We also observe that replacing $\triangle$ 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].