The epsilon-t-net problem

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 . When t = 1, this corresponds to the epsilon-net problem.

We prove that any sufficiently large hypergraph with VC-dimension d admits an epsilon--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--nets. Time permitting, we will also discuss explicit algorithms for finding epsilon-nets and epsilon--nets.

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