A simple proof of optimal epsilon nets (Q1715082): Difference between revisions

Given a set system $(X,\mathcal{R})$ and any $Y \subseteq X$, $\mathcal{R} \vert_Y$ is defined to be $\{ Y \cap R \mid R \in \mathcal{R}\}$. The VC-dimension VC-$\dim (\mathcal{R})$ of $\mathcal{R}$ is the size of the largest $Y \subseteq X$ for which $\mathcal{R} \vert_Y =2^Y$.\par For $\varepsilon > 0$, an $\varepsilon$-net for a set system $(X,\mathcal{R})$ is a set $N \subseteq X$ such that $N \cap R \ne \emptyset$ for all $R \in \mathcal{R}$ with $\vert R\vert \geq \varepsilon \vert X\vert $.\par A set system $(X,\mathcal{R})$ has shallow-cell complexity $\varphi_{\mathcal{R}}(\cdot,\cdot)$ if for any $Y \subseteq X$, the number of subsets in $\mathcal{R}\vert_Y$ of size at most $\ell$ is $\vert Y\vert \cdot \varphi_{\mathcal{R}}(\vert Y\vert ,\ell)$.\par The size of the smallest $\varepsilon$-nets for set systems has been settled in terms of shallow-cell complexity. The authors give a short proof of this result based on the $\varepsilon$-net bound of \textit{D. Haussler} and \textit{E. Welzl} [Discrete Comput. Geom. 2, 127--151 (1987; Zbl 0619.68056)] together with the packing lemma of \textit{D. Haussler} [J. Comb. Theory, Ser. A 69, No. 2, 217--232 (1995; Zbl 0818.60005)]. More precisely, the authors prove the following. Let $(X,\mathcal{R})$, $\vert X\vert = n$, be a set system with VC-$\dim (\mathcal{R}) = d$ and shallow-cell complexity $\varphi_{\mathcal{R}}(\cdot,\cdot)$, where $\varphi_{\mathcal{R}}(\cdot,\cdot)$ is a non-decreasing function in the first variable. Then there exists an $\varepsilon$-net for $\mathcal{R}$ of size $O(\frac{1}{\varepsilon} \log \varphi(\frac{8d}{\varepsilon},24d) + \frac{d}{\varepsilon})$.