The epsilon-t-net problem

Seminar
Speaker
Chaya Keller (Ariel University)
Date
19/01/2020 - 15:30 - 14:00Add to Calendar 2020-01-19 14:00:00 2020-01-19 15:30:00 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. Room 201, Math and CS Building (Bldg. 216) אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Room 201, Math and CS Building (Bldg. 216)
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.

Last Updated Date : 14/01/2020