Monday, February 20th, 2012 | 4pm-5pm | Burnside 1205 |

School of Computer Science, Charles University

Points covered by many simplices

Boros and Furedi (for d=2) and Barany (for arbitrary d) proved that there exists a constant c_{d}>0 such that for every set P of n points in R^{d}
in general position, there exists a point of R^{d} contained in at least
c_{d} [n choose d+1] (d+1)-simplices with vertices at the points of P.
Gromov [Geom. Funct. Anal. 20 (2010), 416-526] improved the lower bound
on c_{d} by topological means. Using the framework of flag algebras
developed by Razborov, we improve one of the quantities
appearing in Gromov's approach and thereby provide a new stronger
lower bound on c_{d} for arbitrary d. In particular, we improve
the lower bound on c_{3} from 0.06332 due to Matousek and Wagner
to more than 0.07480 (the known upper bound on c_{3} is 0.09375).

This is joint work with Lukas Mach and Jean-Sebastien Sereni.