An uniform version of Dvir and Moran's theorem

Abstract

Dvir and Moran proved the following upper bound for the size of a family $\mbox{$\cal F$}$ of subsets of $[n]$ with $\mbox{Vdim}(\mbox{$\cal F$} Δ\mbox{$\cal F$})\leq d$. Let $d\le n$ be integers. Let $\mbox{$\cal F$}$ be a family of subsets of $[n]$ with $\mbox{Vdim}(\mbox{$\cal F$} Δ\mbox{$\cal F$})\leq d$. Then \[ \left|\mbox{$\mathcal{F}$}\right|\le 2\sum_{k=0}^{\lfloor d/2 \rfloor}\binom nk. \] Our main result is the following uniform version of Dvir and Moran's result. Let $d\le n$ be integers. Let $\mbox{$\cal F$}$ be an uniform family of subsets of $[n]$ with $\mbox{Vdim}(\mbox{$\cal F$} Δ\mbox{$\cal F$})\leq d$. Then \[ \left|\mbox{$\mathcal{F}$}\right|\le 2 {n \choose \lfloor d/2 \rfloor}. \] Denote by ${\mathbf{v}}_{\mathbf{F}}\in \{0,1{\}}^n$ the characteristic vector of a set $F\subseteq [n]$. Our proof is based on the following uniform version of Croot-Lev-Pach Lemma: Let $0\le d\le n$ be integers. Let $\mbox{$\cal H$}$ be a $k$-uniform family of subsets of $[n]$. Let $\mathbb{F}$ be a field. Suppose that there exists a polynomial $P(x_1,\dots ,x_n,y_1,\dots ,y_n)\in \mathbb{F}[x_1,\dots ,x_n,y_1,\dots ,y_n]$ with $\mbox{deg}(P)\leq d$ such that $P({\mathbf{v}}_{\mathbf{F}},{\mathbf{v}}_{\mathbf{F}})\ne 0$ for each $F\in \mbox{$\cal H$}$ and $P({\mathbf{v}}_{\mathbf{F}},{\mathbf{v}}_{\mathbf{G}})=0$ for each $F\ne G\in \mbox{$\cal H$}$. Then \[ \left|\mbox{$\mathcal{H}$}\right|\le 2 {n \choose \lfloor d/2 \rfloor}. \]

10 pages