Article ID Journal Published Year Pages File Type
8903102 Discrete Mathematics 2018 12 Pages PDF
Abstract
Finally, we give another proof of the previous result based on a combinatorial observation: an extension of the Epsilon-net Theorem of Haussler and Welzl. We show that for a hypergraph of bounded Vapnik-Chervonenkis dimension, in which each edge is of a certain measure, there is a not-too large transversal set which does not intersect any edge too many times.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,