Theorems of Carathéodory, Helly, and Tverberg without dimension

Imre Bárány, Rényi Institute, Budapest and University College London

Date and time: 6pm, Tuesday, April 2, 2019

Place: Courant Institute, WWH1314

We prove a no-dimensional version of Carathédory's theorem: given an $n$-element set $P\subset \mathbf{R}^d$, a point $p \in \mathop{\text{conv}}(P)$, and an integer $r\le d$, $r \le n$, there is a subset $Q \subset P$ of $r$ elements such that the distance between $p$ and $\mathop{\text{conv}}(Q)$ is less than $\mathop{\text{diam}}(P)/\sqrt{2r}$. We also give effective algorithms that find such a set $Q$. An analogous no-dimension Helly theorem says that, given k⩽d and a finite family $F$ of convex bodies, all contained in the Euclidean unit ball of $\mathbf{R}^d$, such that every $k$-tuple of the in the family has a point in common, there is a point q∈R^d which is closer than $1/\sqrt{k}$ to every set in $F$. This result has several colourful and fractional consequences. Similar versions of Tverberg's theorem and some of their extensions are also established.

This is joint work with Karim Adiprasito, Nabil H. Mustafa, and Tamás Terpai.