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

DOI10.1007/S00454-012-9419-3zbMATH Open1262.05151DBLPjournals/dcg/KralMS12arXiv1108.0297OpenAlexW3098813812WikidataQ57601368 ScholiaQ57601368MaRDI QIDQ452003FDOQ452003

Authors: Daniel Král', Lukáš Mach, Jean-Sébastien Sereni 

Publication date: 19 September 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1108.0297

Recommendations

• On Gromov's method of selecting heavily covered points
• Hitting simplices with points in \(\mathbb R^{3}\)
• scientific article; zbMATH DE number 1305394
• An Upper Bound for the d-Dimensional Analogue of Heilbronn's Triangle Problem
• Stabbing simplices by points and flats

zbMATH Keywords

Cofilling profilesCovering points by simplicesFlag algebrasBoros-Füredi-Bárány-Pach-Gromov theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Extremal combinatorics (05D99)

Cites Work

• Limits of dense graph sequences
• On the number of pentagons in triangle-free graphs
• Non-three-colourable common graphs exist
• On 3-hypergraphs with forbidden 4-vertex configurations
• Hypergraphs do jump
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Flag algebras
• The number of triangles covering the center of an \(n\)-set
• A generalization of Caratheodory's theorem
• A simpler proof of the Boros-Füredi-Bárány-Pach-Gromov theorem
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
• On Gromov's method of selecting heavily covered points
• Stabbing simplices by points and flats
• A point in many triangles
• Improving the first selection lemma in \(\mathbb{R}^3\)

Cited In (27)

• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• A proof of the Oja depth conjecture in the plane
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• On Gromov's method of selecting heavily covered points
• Upper bounds for stabbing simplices by a line
• Sharp bounds for decomposing graphs into edges and triangles
• Decomposing graphs into edges and triangles
• Closing in on Hill's conjecture
• \(k\)-centerpoints conjectures for pointsets in \(\mathbb{R}^d\)
• A new bound for the 2/3 conjecture
• Maximum number of almost similar triangles in the plane
• Minimum number of edges that occur in odd cycles
• Solving Turán's tetrahedron problem for the ℓ2$\ell _2$‐norm
• Finitely forcible graphons with an almost arbitrary structure
• Bounds for Pach's selection theorem and for the minimum solid angle in a simplex
• Weak regularity and finitely forcible graph limits
• Finitely forcible graphons and permutons
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• A note on lower bounds for colourful simplicial depth
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• Inducibility of directed paths
• Finitely forcible graph limits are universal
• Rainbow triangles in three-colored graphs
• A slight improvement to the colored Bárány's theorem
• Compactness and finite forcibility of graphons
• On crossing numbers of complete tripartite and balanced complete multipartite graphs
• Positive-fraction intersection results and variations of weak epsilon-nets

This page was built for publication: A new lower bound based on Gromov's method of selecting heavily covered points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q452003)