##### Personal tools
You are here: Home 2020 An Extension of Epsilon-nets for Hypergraphs with Bounded VC-dimension
« September 2020 »
September
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
27282930

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

### 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.