Graph Theory Seminar
Friday, September 16, 2011 - 15:05
1 hour (actually 50 minutes)
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!/(d+1)!(n-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 methods from extremal combinatorics, 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.07509 (the known upper bound on c_3 is 0.09375). Joint work with Lukas Mach and Jean-Sebastien Sereni.