@inproceedings{0fead3c784c2493e9c862516cd51171d,

title = "The ε-T-net problem",

abstract = "We study a natural generalization of the classical ε-net problem (Haussler-Welzl 1987), which we call the ε-t-net problem: Given a hypergraph on n vertices and parameters t and ε ≥ nt, find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least εn contains a set in S. When t = 1, this corresponds to the ε-net problem. We prove that any sufficiently large hypergraph with VC-dimension d admits an ε-t-net of size O((1+log ε t)d log 1 ε). For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of O(1 ε)-sized ε-t-nets. We also present an explicit construction of ε-t-nets (including ε-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of ε-nets (i.e., for t = 1), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.",

keywords = "Epsilon-nets, Geometric hypergraphs, Linear union complexity, VC-dimension",

author = "Noga Alon and Bruno Jartoux and Chaya Keller and Shakhar Smorodinsky and Yelena Yuditsky",

year = "2020",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SoCG.2020.5",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Sergio Cabello and Chen, {Danny Z.}",

booktitle = "36th International Symposium on Computational Geometry, SoCG 2020",

address = "Germany",

note = "36th International Symposium on Computational Geometry, SoCG 2020 ; Conference date: 23-06-2020 Through 26-06-2020",

}