Daniel Kral

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₃ from 0.06332 due to Matousek and Wagner to more than 0.07480 (the known upper bound on c₃ is 0.09375).

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