A simple proof of optimal epsilon nets
type: Item
instance of: scholarly article
title: A simple proof of optimal epsilon nets
zbMATH Open document ID: 1424.52020
author: Nabil H. Mustafa
author: Kunal Dutta
author: Arijit Ghosh
published in: Combinatorica
publication date: 2019-02-01T00:00:00Z
review text: 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})$.
Mathematics Subject Classification ID: 52C45
Mathematics Subject Classification ID: 05D15
Mathematics Subject Classification ID: 52B55
zbMATH DE Number: 7011215
zbMATH Keywords: set system
zbMATH Keywords: VC-dimension
zbMATH Keywords: $\varepsilon$-net
zbMATH Keywords: shallow-cell complexity
MaRDI profile type: Publication
full work available at URL: s00493-017-3564-5
OpenAlex ID: W2587329907
DOI: 10.1007/S00493-017-3564-5
Recommended article: Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
Recommended article: New Lower Bounds for ϵ-nets
Recommended article: Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems
Recommended article: Q4580113
Recommended article: Two proofs for shallow packings
Recommended article: Two Proofs for Shallow Packings
Recommended article: Q5091247
Recommended article: On the size of set systems on \([n]\) not containing weak \((r,\Delta)\)-systems
Recommended article: On Extremal Set Partitions in Cartesian Product Spaces
Recommended article: Q4208235
description: scientific article; zbMATH DE number 7011215