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

DOI10.1007/s00454-012-9419-3zbMath1262.05151arXiv1108.0297OpenAlexW3098813812WikidataQ57601368 ScholiaQ57601368MaRDI QIDQ452003

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

Publication date: 19 September 2012

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

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

zbMATH Keywords

Boros-Füredi-Bárány-Pach-Gromov theoremCofilling profilesCovering points by simplicesFlag algebras

Mathematics Subject Classification ID

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

Related Items

Finitely forcible graph limits are universal ⋮ Maximum number of almost similar triangles in the plane ⋮ k-Centerpoints Conjectures for Pointsets in ℝd ⋮ A note on lower bounds for colourful simplicial depth ⋮ Rainbow triangles in three-colored graphs ⋮ Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle ⋮ Solving Turán's tetrahedron problem for the ℓ2$\ell _2$‐norm ⋮ Minimum Number of Monotone Subsequences of Length 4 in Permutations ⋮ On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs ⋮ Finitely forcible graphons with an almost arbitrary structure ⋮ A proof of the Oja depth conjecture in the plane ⋮ Finitely forcible graphons and permutons ⋮ Upper bounds for stabbing simplices by a line ⋮ A slight improvement to the colored Bárány's theorem ⋮ Positive-fraction intersection results and variations of weak epsilon-nets ⋮ A New Bound for the 2/3 Conjecture ⋮ Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube ⋮ On Gromov's method of selecting heavily covered points ⋮ Bounds for Pach's selection theorem and for the minimum solid angle in a simplex ⋮ Decomposing Graphs into Edges and Triangles ⋮ Minimum number of edges that occur in odd cycles ⋮ Closing in on Hill's Conjecture ⋮ Weak regularity and finitely forcible graph limits ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Compactness and finite forcibility of graphons ⋮ Inducibility of directed paths

Cites Work

• 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
• Limits of dense graph sequences
• The number of triangles covering the center of an \(n\)-set
• A generalization of Caratheodory's theorem
• On the number of pentagons in triangle-free graphs
• A point in many triangles
• 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
• Improving the first selection lemma in R ³
• Flag algebras
• Counting flags in triangle-free digraphs