Big line or big convex polygon

2024/05/06 by David Conlon, Jacob Fox, Conlon, David +9
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Mathematics and Applications

paper · pdf · doi:10.48550/arxiv.2405.03455

openalex publication_date 2024/05/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

Let ES_ℓ(n) be the minimum N such that every N-element point set in the plane contains either ℓ collinear members or n points in convex position. We prove that there is a constant C>0 such that, for each ℓ, n ≥ 3, (3ℓ - 1) ⋅ 2^n-5 lt; ES_ℓ(n) lt; ℓ² ⋅ 2^{n+ C√(nlog n)}. A similar extension of the well-known Erd\H os--Szekeres cups-caps theorem is also proved.

Related

• Big convex polytopes or rich hyperplanes
• On the Erdos-Szekeres convex polygon problem
• Convex polytopes from fewer points
• Happy Ending or Many Concurrent Lines
• On a conjecture of Erdős and Szekeres