A Sauer-Shelah-Perles lemma for sumsets

Zeev Dvir, Shay Moran

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

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

Original languageEnglish (US)
Article number#P4.38
JournalElectronic Journal of Combinatorics
Volume25
Issue number4
DOIs
StatePublished - 2018

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A Sauer-Shelah-Perles lemma for sumsets'. Together they form a unique fingerprint.

  • Cite this