A new lower bound based on Gromov's method of selecting heavily covered points

Abstract

Boros and Furedi (for d=2) and Barany (for abritrary 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 c_d n!/(d+1)!(n-d-1)! d-simplices with vertices at the points of P. Gromov 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 to more than 0.07480; the best upper bound known on c_3 being 0.09375.

Cited by in corpus (14)

• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• Minimum number of monotone subsequences of length 4 in permutations
• Rainbow triangles in three-colored graphs
• Crossing numbers of complete tripartite and balanced complete multipartite graphs
• Inducibility of directed paths
• Solving Turán's Tetrahedron Problem for the ${\ell }_2$-Norm
• Infinite dimensional finitely forcible graphon
• Elusive extremal graphs
• Bounds for Pach's selection theorem and for the minimum solid angle in a simplex
• Closing in on Hill's conjecture
• Decomposing graphs into edges and triangles
• Maximum Number of Almost Similar Triangles in the Plane
• The dimension of the feasible region of pattern densities