A Sauer-Shelah-Perles Lemma for Sumsets

Electronic Journal Of Combinatorics

Zeev Dvir¹ 

关键词: Extremal combinatorics;    VC dimension;    Polynomial method;   

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

We show that any family of subsets $A\subseteq 2^{[n]}$ satisfies $\lvert A\rvert \leq O\bigl(n^{\lceil{d}/{2}\rceil}\bigr)$, where $d$ is the VC dimension of $\{S\triangle T \,\vert\, S,T\in A\}$, and $\triangle$ is the symmetric difference operator. We

【 授权许可】

Others