Skip to main content

A Sauer-Shelah-Perles Lemma for Sumsets

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

To refer to this page use:
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].
Publication Date: 16-Nov-2018
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
DOI: 10.37236/7945
EISSN: 1077-8926
Pages: P4.38:1 - P4.38:7
Type of Material: Journal Article
Journal/Proceeding Title: The Electronic Journal of Combinatorics
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.