Title: 
Extended VC-dimension and Radon and
Tverberg-type Theorems for Unions of Convex Sets


Abstract:


Radon's theorem is one of the classical starting points of convexity: any set of
$d+2$ points in $\mathbb{R}^d$ can be split into two parts whose convex hulls
intersect.  Equivalently, no matter how one tries to separate the two parts by
convex sets, convexity forces an intersection.

In this talk I will discuss what happens when convex sets are replaced by
unions of a bounded number of convex sets.  This seemingly small change leads to
a natural and surprisingly subtle extension of Radon's theorem, suggested by
Gil Kalai in the 1970s.

For every dimension $d$ and integer $s \geq 1$, we determine, up to the best
possible order of magnitude, the smallest number $f(d,s)$ with the following
property: every set $P$ of $f(d,s)$ points in $\mathbb{R}^d$ admits a partition
$P=A\cup B$ such that every union of $s$ convex sets containing $A$ must meet
every union of $s$ convex sets containing $B$.  When $s=1$ this is exactly
Radon's theorem, with $f(d,1)=d+2$.

The result gives a new Radon-type theorem for a non-convex family of sets. Furthermore, we establish an extension of it to a Tverberg-type theorem for unions of convex sets.
The proofs combine ideas from convexity and combinatorics, and in fact extend
beyond Euclidean space to suitable abstract convexity spaces.

This is joint work with Noga Alon.

Recording Link: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=9ba1051e-2e9f-4e63-9d46-b4340058810b