The epsilon-t-Net Problem

Speaker: Lena Yuditsky (Université Libre de Bruxelles)

Abstract: 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>= t/n, 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(((1+log t)d)/(epsilon)*log 1/epsilon). For some families of geometrically-defined hypergraphs, we prove the existence of O(1/epsilon)-sized epsilon-t-nets.

This is a joint work with Noga Alon, Bruno Jartoux, Chaya Keller and Shakhar Smorodinsky.

Date and time: 07/01/2020 at 14:30 (Paris time)

Link to the talk: https://bbb-temp.grenet.fr/b/lou-9x7-69p