You are here

Computer Science/Discrete Mathematics Seminar II

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.

Featuring

Shay Moran

Speaker Affiliation

University of California, San Diego; Member, School of Mathematics

Affiliation

Mathematics

Event Series

Video

https://video.ias.edu/csdm/2018/0313-ShayMoran
Date & Time
March 13, 2018 | 10:30am12:30pm

Location

Simonyi Hall 101

Categories