Abstract Convexity, Weak Epsilon-Nets, and Radon Number

Let F be a family of subsets over a domain X that is closed under taking intersections. Such structures are abundant in various fields of mathematics such as topology, algebra, analysis, and more. In this talk we will view these objects through the lens of convexity.

We will focus on an abstraction of the notion of weak epsilon nets:
given a distribution on the domain X and epsilon>0,
a weak epsilon net for F is a set of points that intersects any set in F with measure at least epsilon.

The family of convex subsets of R^d have weak epsilon-nets of size that is independent on the domain distribution; this was shown by [Barany et al ’90], [Alon et al ’92], and [Chazelle et al ’93].

The main result I’ll present shows that the Radon number (an abstraction of Radon’s Theorem for convex sets) characterizes the existence of weak nets for arbitrary intersection-closed families that satisfy a mild separability condition. Our bounds on the size are weaker than what is known for euclidean convex sets but apply more generally.

Based on a joint work with Amir Yehudayoff.