# 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