Shay Moran

collaborators

2 papers

math.CO2018

A Sauer-Shelah-Perles Lemma for Lattices

Stijn Cambie, Bogdan Chornomaz, Zeev Dvir +2

We study lattice-theoretical extensions of the celebrated Sauer-Shelah-Perles Lemma. We conjecture that a general Sauer-Shelah-Perlem Lemma holds for a lattice $L$ if and only if $…

math.CO2018

A Sauer-Shelah-Perles Lemma for Sumsets

Zeev Dvir, Shay Moran

We show that any family of subsets $A \subseteq 2^{[n]}$ satisfies $∣ A ∣ \leq O (n^{⌈ d / 2 ⌉})$ , where $d$ is the VC dimension of $\{S\triangle T \,\ve…