A Sauer-Shelah-Perles Lemma for Sumsets
share
We show that any family of subsets A⊆ 2^[n] satisfies A≤ O(n^d/2), where d is the VC dimension of {S T S,T∈ A}, and is the symmetric difference operator. We also observe that replacing by either ∪ or ∩ fails to satisfy an analogous statement. Our proof is based on the polynomial method; specifically, on an argument due to [Croot, Lev, Pach '17].
READ FULL TEXT