A Sauer-Shelah-Perles Lemma for Sumsets

06/14/2018

∙

by   Zeev Dvir, et al.

∙

0

∙

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].