论文标题
$ε$ - $ T $ -NET问题
The $ε$-$t$-Net Problem
论文作者
论文摘要
We study a natural generalization of the classical $ε$-net problem (Haussler--Welzl 1987), which we call the "$ε$-$t$-net problem": Given a hypergraph on $n$ vertices and parameters $t$ and $ε\geq \frac t n$, find a minimum-sized family $S$ of $t$-element subsets of vertices such that each hyperedge of size at least $εn$包含$ S $中的一组。当$ t = 1 $时，这对应于$ε$ -NET问题。 我们证明，使用VC-Dimension $ d $的任何足够大的超图都允许$ε$ -T $ -NET大小$ o（\ frac {（1+ \ log t）d} d}ε\ log \ log \ frac {1}ε）$。对于一些几何定义的超图（例如具有线性联合复杂性的区域的双重高图）的家庭，我们证明存在$ o（\ frac {1}ε）$ - 大小$ε$ - $ t $ -nets。 我们还提供了$ε$ - $ t $ -nets（包括$ε$ -NETS）的明确结构，用于具有有限的VC-dimension的超图。与$ε$ -NET的特殊情况（即$ t = 1 $）的先前构造相比，它不依赖高级降低技术。为此，我们介绍了具有独立利益的VC-Dimension概念的一种变体。
We study a natural generalization of the classical $ε$-net problem (Haussler--Welzl 1987), which we call the "$ε$-$t$-net problem": Given a hypergraph on $n$ vertices and parameters $t$ and $ε\geq \frac t n$, find a minimum-sized family $S$ of $t$-element subsets of vertices such that each hyperedge of size at least $εn$ contains a set in $S$. When $t=1$, this corresponds to the $ε$-net problem. We prove that any sufficiently large hypergraph with VC-dimension $d$ admits an $ε$-$t$-net of size $O(\frac{ (1+\log t)d}ε \log \frac{1}ε)$. 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}ε)$-sized $ε$-$t$-nets. We also present an explicit construction of $ε$-$t$-nets (including $ε$-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of $ε$-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.
