On Weak ϵ-Nets and the Radon Number

We show that the Radon number characterizes the existence of weak nets in separable convexity spaces (an abstraction of the Euclidean notion of convexity). The construction of weak nets when the Radon number is finite is based on Helly’s property and on metric properties of VC classes. The lower bou...

Full description

Saved in:
Bibliographic Details
Published in:Discrete & computational geometry 2020-12, Vol.64 (4), p.1125-1140
Main Authors: Moran, Shay, Yehudayoff, Amir
Format: Article
Language:English
Subjects:
Combinatorics
Computational Mathematics and Numerical Analysis
Convexity
Lower bounds
Mathematics
Mathematics and Statistics
Radon
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that the Radon number characterizes the existence of weak nets in separable convexity spaces (an abstraction of the Euclidean notion of convexity). The construction of weak nets when the Radon number is finite is based on Helly’s property and on metric properties of VC classes. The lower bound on the size of weak nets when the Radon number is large relies on the chromatic number of the Kneser graph. As an application, we prove an amplification result for weak ϵ -nets.
ISSN:0179-5376
1432-0444
DOI:10.1007/s00454-020-00222-y