Combinatorics: Chaya Keller (Ariel)

Title: The epsilon-t-net problem


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

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

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


Mon, 27/01/2020 - 10:00 to 12:00


C-400, CS building