2024/09/25 by John Mackey, Bernardo Subercaseaux, Mackey, John +1
Engineering · Materials Science · Physics and Astronomy · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Crystallography and Radiation Phenomena #Discrete Mathematics (cs.DM) #Electron and X-Ray Spectroscopy Techniques #FOS: Computer and information sciences #FOS: Mathematics #Robotic Mechanisms and Dynamics
paper · pdf · doi:10.48550/arxiv.2409.17098
openalex publication_date 2024/09/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Erdős and Guy initiated a line of research studying μk(n), the minimum number of convex k-gons one can obtain by placing n points in the plane without any three of them being collinear. Asymptotically, the limits ck := limn→ ∞ μk(n)/\binomnk exist for all k, and are strictly positive due to the Erdős-Szekeres theorem. This article focuses on the case k=5, where c5 was known to be between 0.0608516 and 0.0625 (Goaoc et al., 2018; Subercaseaux et al., 2023). The lower bound was obtained through the Flag Algebra method of Razborov using semi-definite programming. In this article we prove a more modest lower bound of (5√(5)-11)/(4) ≈ 0.04508 without any computation; we exploit``planar-point equations'' that count, in different ways, the number of convex pentagons (or other geometric objects) in a point placement. To derive our lower bound we combine such equations by viewing them from a statistical perspective, which we believe can be fruitful for other related problems.