# The epsilon-t-net problem

יום א', 19/01/2020 - 14:00
Speaker:
Seminar:
Place:
Abstract:

In this talk we study a natural generalization of the classical epsilon-net problem (Haussler-Welzl 1987), which we call 'the epsilon-t-net problem': Given a hypergraph on n vertices and parameters t and epsilon, find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least epsilon n contains a set in $S$. When t = 1, this corresponds to the epsilon-net problem.

We prove that any sufficiently large hypergraph with VC-dimension d admits an epsilon-$t$-net of size O_t(d/epsilon log(1/epsilon)), thus obtaining a sharp generalization of the classical epsilon-net theorem. For some families of geometrically-defined hypergraphs, we prove the existence of O(1/epsilon)-sized epsilon-$t$-nets. Time permitting, we will also discuss explicit algorithms for finding epsilon-nets and epsilon-$t$-nets.

Joint work with Noga Alon, Bruno Jartoux, Shakhar Smorodinsky and Yelena Yuditsky.