A Sauer-Shelah-Perles Lemma for Sumsets

Abstract

We show that any family of subsets A 2^[n] satisfies A O(n^d/2), where d is the VC dimension of 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].

Tasks

Reproductions