ε-t-net size and computation
The $\varepsilon$-$t$-Net Problem · arXiv:2003.07061
Status open high confidence
The problem asks how small the smallest $\varepsilon$-$t$-nets for a hypergraph $H$ can be and whether they can be computed efficiently. The source paper proved existence of $\varepsilon$-$t$-nets of size $O((1+\log t)d/\varepsilon \cdot \log(1/\varepsilon))$ for VC-dimension-$d$ hypergraphs and $O(1/\varepsilon)$ for certain geometric classes; whether these bounds are tight and whether efficient algorithms exist in general remains open. A 2024 paper by Keller and Smorodinsky (arXiv:2311.13662, SoCG 2024) applies $\varepsilon$-$t$-nets as a tool to Zarankiewicz’s problem, extending the utility of the framework but not resolving the original minimization or algorithmic questions.
Cited literature (1)
-
Applies $\varepsilon$-$t$-nets as a tool to Zarankiewicz’s problem, obtaining a sharp $O(n)$ bound for intersection graphs of two families of pseudo-discs and an $O(n\log n/\log\log n)$ bound for axis-parallel rectangles, demonstrating the power of the $\varepsilon$-$t$-net framework but not resolving the original question on minimum net sizes.
Reviewer notes. The ε-t-Net Problem is the core open problem of the paper; the specific questions on tight bounds for general hypergraphs and efficient computation remain unresolved. The journal version appeared in Discrete & Computational Geometry (2022), DOI 10.1007/s00454-022-00376-x. A 2024 SoCG paper by two of the original authors (Keller and Smorodinsky) uses ε-t-nets as a productive combinatorial tool for Zarankiewicz-type problems in geometry. No paper was found that directly proves or disproves optimal bounds for the general ε-t-net minimization problem.
Context
Given a finite hypergraph $H=(V,E)$, a positive integer $t$, and $\varepsilon\in(t/|V|,1)$, an $\varepsilon$-$t$-net is a family $S\subseteq\binom{V}{t}$ of $t$-element subsets of $V$ such that every hyperedge $e\in E$ with $|e|\geq\varepsilon|V|$ contains some $s\in S$. The problem generalises the classical $\varepsilon$-net problem ($t=1$) and the Mnet notion ($t=\Theta(\varepsilon|V|)$), and arises naturally in secret sharing and other combinatorial contexts.
Notes. Stated as an explicitly labelled Problem environment in Section 1.2. PDF source causes epsilon to render as (cid:15) throughout, but the statement itself is unambiguous.
Source paper
The $ε$-$t$-Net Problem
Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky · 2020-03-16
https://arxiv.org/abs/2003.07061
PDF source