The \epsilon-t-Net Problem

DOI10.1007/S00454-022-00376-XMaRDI QIDQ6504950arXivFDO

Authors Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00454-022-00376-X

Abstract: We study a natural generalization of the classical $epsilon$-net problem (Haussler--Welzl 1987), which we call the "$epsilon$-$t$-net problem": Given a hypergraph on $n$ vertices and parameters $t$ and $epsilongeqfractn$, find a minimum-sized family $S$ of $t$-element subsets of vertices such that each hyperedge of size at least $epsilonn$ contains a set in $S$. When $t=1$, this corresponds to the $epsilon$-net problem. We prove that any sufficiently large hypergraph with VC-dimension $d$ admits an $epsilon$-$t$-net of size $O(frac(1+logt)depsilonlogfrac1epsilon)$. For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of $O(frac1epsilon)$-sized $epsilon$-$t$-nets. We also present an explicit construction of $epsilon$-$t$-nets (including $epsilon$-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of $epsilon$-nets (i.e., for $t=1$), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.

This page was built for publication: The $\epsilon$-$t$-Net Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6504950)