The epsilon-t-net problem

יום א', 19/01/2020 - 14:00

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.