TY - JOUR
T1 - A Sauer-Shelah-Perles lemma for sumsets
AU - Dvir, Zeev
AU - Moran, Shay
N1 - Funding Information:
∗Research supported by NSF CAREER award DMS-1451191 and NSF grant CCF-1523816. †Research supported by the National Science Foundation under agreement No. CCF-1412958 and by the Simons Foundations.
Publisher Copyright:
© Zeev Dvir and Shay Moran.
PY - 2018
Y1 - 2018
N2 - 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].
AB - 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].
UR - http://www.scopus.com/inward/record.url?scp=85058517742&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85058517742&partnerID=8YFLogxK
U2 - 10.37236/7945
DO - 10.37236/7945
M3 - Article
AN - SCOPUS:85058517742
SN - 1077-8926
VL - 25
JO - Electronic Journal of Combinatorics
JF - Electronic Journal of Combinatorics
IS - 4
M1 - #P4.38
ER -