To refer to this page use:
http://arks.princeton.edu/ark:/88435/pr1vc1x| 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.