# An Extension of Epsilon-nets for Hypergraphs with Bounded VC-dimension

### Wednesday, June 17th, 2020, 16:10

~~Checkpoint 480~~

### Zoom: Request the link from Dan Halperin or Golan Levy

### An Extension of Epsilon-nets for Hypergraphs with Bounded VC-dimension

### Shakhar Smorodinsky

### Abstract:

In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population or a probability distribution. For a one dimensional data set, it may be thought of as the "middle" value. A far more general notion is the classical notion of $\epsilon$-net in hypergraphs.

We study the following yet more general notion: Let $H=(V,E)$ be a hypergraph $0 < \epsilon \leq 1$ a real and $t \geq 1$ an integer.

We call a family $N$ of subsets (of $V$) of cardinality $t$ an {\em $\epsilon-t$-net} if every hyperedge $S \in E$ with size at least $\epsilon |V|$ contains at least one set from $N$. When $t=1$ this is the classical notion of $\epsilon$-net.

We show that for any constant integers $t,d$ any hypergraph with VC-dimension $d$ admits an $\epsilon-t$-net of size $O(\frac{d}{\epsilon} \log \frac{1}{\epsilon})$.

Joint work with Noga Alon, Bruno Jartoux, Chaya Keller and Yelena Yuditsky.