Theorems of Caratheodory, Helly, and Tverberg without dimension

-
Imre Bárány,Renyi Institute, Budapest and University College, London
Fine Hall 214

We prove a no-dimensional version of Carathedory's theorem: given an n-element set P in R^d, a point a in conv P, and an integer r at most min (d,n), there is a subset Q of P of r elements such that the distance between the point a and conv Q is less than $diam P/\sqrt {2r}$.  An analogous no-dimension Helly theorem says that, given k (at most d) and a finite family F of convex bodies, all contained in the Euclidean unit ball of R^d, there is a point q in 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. I intend to cover algorithmic aspects of these results. This is joint work with Karim Adiprasito, Nabil H. Mustafa, and Tamas Terpai.

Imre Barany is a research professor at the Renyi Institute in Budapest and the Astor professor of pure mathematics at University College London. His main interest is discrete and convex geometry, and its applications in geometry of numbers, computer science, operations research, game theory and elsewhere.