A Sauer-Shelah-Perles lemma for sumsets

Zeev Dvir; Shay Moran

doi:10.37236/7945

A Sauer-Shelah-Perles lemma for sumsets

Zeev Dvir, Shay Moran

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Article number	#P4.38
Journal	Electronic Journal of Combinatorics
Volume	25
Issue number	4
DOIs	https://doi.org/10.37236/7945
State	Published - 2018
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.37236/7945

Cite this

@article{fa20652809fd49f4881fbb58b6e79114,

title = "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 {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 {\textquoteright}17].",

author = "Zeev Dvir and Shay Moran",

note = "Publisher Copyright: {\textcopyright} Zeev Dvir and Shay Moran.",

year = "2018",

doi = "10.37236/7945",

language = "English (US)",

volume = "25",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "4",

}

TY - JOUR

T1 - A Sauer-Shelah-Perles lemma for sumsets

AU - Dvir, Zeev

AU - Moran, Shay

N1 - 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 -

A Sauer-Shelah-Perles lemma for sumsets

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this