Publication details
A New Lower Bound Based on Gromov's Method of Selecting Heavily Covered Points
| Authors | |
|---|---|
| Year of publication | 2012 |
| Type | Article in Periodical |
| Magazine / Source | DISCRETE & COMPUTATIONAL GEOMETRY |
| Citation | |
| Doi | http://dx.doi.org/10.1007/s00454-012-9419-3 |
| Keywords | Flag algebras; Covering points by simplicies; Cofilling profiles; Boros-Furedi-Barany-Pach-Gromov theorem |
| Description | Boros and Furedi (for d=2) and Barany (for arbitrary d) proved that there exists a positive real number c (d) 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 d-simplices with vertices at the points of P. Gromov improved the known 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 to more than 0.07480; the best upper bound known on c (3) being 0.09375. |