New Sufficient Conditions for Linear-Sized Epsilon-Nets and $(p,2)$-Theorems

Abstract

An $\hat{I}\mu$-net theorem for a hypergraph upper bounds the minimum size of a vertex set that pierces all $\hat{I}\mu$-heavy hyperedges. A $(p,2)$-theorem bounds from above the minimum size of a vertex set that pierces all hyperedges, in terms of the maximum size of a set of pairwise disjoint hyperedges. Numerous works studied $\hat{I}\mu$-net theorems and $(p,2)$-theorems that guarantee the existence of small-sized piercing sets. We focus on the question: In which settings the asymptotically smallest possible piercing sets -- i.e., $\hat{I}\mu$-nets of size $O(\frac{1}{\hat{I}}\mu )$ and piercing sets of size $O(p)$ in $(p,2)$-theorems, are guaranteed? We obtain several sufficient criteria for the existence of such linear $\hat{I}\mu$-net theorems and $(p,2)$-theorems that unveil interesting connections to graph theory and improve and generalize several previous results. Most notably, we exhibit an unexpected relation of $\hat{I}\mu$-nets to the classical Zarankiewicz's problem in graph theory. We show that a linear bound in the Zarankiewicz-type problem that asks for the maximum size of a bipartite graph with no copy of $K_{2,t}$, implies a linear $\hat{I}\mu$-net theorem for the corresponding neighborhood hypergraph. We also show that hypergraphs with a hereditarily linear-sized Delaunay graph admit an almost linear $(p,2)$-theorem, and deduce that incidence hypergraphs of non-piercing regions in the plane admit a linear $(p,2)$-theorem, significantly improving previous results on such hypergraphs. Our work presents a landscape of sufficient conditions for the existence of linear $\hat{I}\mu$-net theorems and $(p,2)$-theorems, with complex interrelations between them. Many of the interrelations are still unknown and call for future research.

16 pages, 1 figure. This version merges the previous one (which contained only $(p,2)$ theorems) with new results on linear-sized ε-nets and additional results. The title of the paper has changed accordingly