The $\varepsilon$-$t$-Net Problem

We study a natural generalization of the classical $\varepsilon$-net problem (Haussler–Welzl 1987), which we call the $\varepsilon$-$t$-net problem: Given a hypergraph on $n$ vertices and parameters $t$ and $\varepsilon\ge \frac{t}{n}$, find a minimum-sized family $S$ of $t$-element subsets of vertices such that each hyperedge of size at least $\varepsilon n$ contains a set in $S$. When $t=1$, this corresponds to the $\varepsilon$-net problem.

We prove that any sufficiently large hypergraph with VC-dimension $d$ admits an $\varepsilon$-$t$-net of size $O(\frac{(1+\log t)d}{\varepsilon} \log \frac{1}{\varepsilon})$. For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of $O(\frac{1}{\varepsilon})$-sized $\varepsilon$-$t$-nets.

We also present an explicit construction of $\varepsilon$-$t$-nets (including $\varepsilon$-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of $\varepsilon$-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.

Joint work with Noga Alon, Bruno Jartoux, Chaya Keller and Shakhar Smorodinsky.