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 cd>0 such that for every set P of n points in Rd in general position, there exists a point of Rd contained in at least cd [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 cd 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 cd for arbitrary d. In particular, we improve the lower bound on c3 from 0.06332 due to Matousek and Wagner to more than 0.07480 (the known upper bound on c3 is 0.09375).

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

Winter 2012 Schedule