A Sauer-Shelah-Perles Lemma for Sumsets

Author(s): Dvir, Zeev; Moran, Shay

Download

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1vc1x

Full metadata record

DC Field	Value	Language
dc.contributor.author	Dvir, Zeev	-
dc.contributor.author	Moran, Shay	-
dc.date.accessioned	2021-10-08T19:46:13Z	-
dc.date.available	2021-10-08T19:46:13Z	-
dc.date.issued	2018-11-16	en_US
dc.identifier.citation	Dvir, Zeev, and Shay Moran. "A Sauer-Shelah-Perles Lemma for Sumsets." The Electronic Journal of Combinatorics 25, no. 4 (2018): pp. P4.38:1-P4.38:7. doi:10.37236/7945	en_US
dc.identifier.uri	http://arks.princeton.edu/ark:/88435/pr1vc1x	-
dc.description.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].	en_US
dc.format.extent	P4.38:1 - P4.38:7	en_US
dc.language.iso	en_US	en_US
dc.relation.ispartof	The Electronic Journal of Combinatorics	en_US
dc.rights	Final published version. This is an open access article.	en_US
dc.title	A Sauer-Shelah-Perles Lemma for Sumsets	en_US
dc.type	Journal Article	en_US
dc.identifier.doi	10.37236/7945	-
dc.identifier.eissn	1077-8926	-
pu.type.symplectic	http://www.symplectic.co.uk/publications/atom-terms/1.0/journal-article	en_US

Files in This Item:

File	Description	Size	Format
LemmaForSumsets.pdf		276.13 kB	Adobe PDF	View/Download