Published March 2026
| Version Published
Journal Article
Big line or big convex polygon
-
1.
California Institute of Technology
-
2.
Stanford University
-
3.
Princeton University
-
4.
University of Illinois at Chicago
-
5.
University of California, San Diego
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) < ESℓ(n) < ℓ² ⋅ 2^(n + C √n log n). A similar extension of the well-known Erdős–Szekeres cups-caps theorem is also proved.
Copyright and License
© 2025 Published by Elsevier B.V.
Acknowledgement
This research was initiated during a visit to the American Institute of Mathematics under their SQuaREs program. We are grateful to Sam Spiro for pointing out a typographical error in a previous version of this paper.
Funding
Research supported by NSF Awards DMS-2054452 and DMS-2348859.
Research supported by NSF Award DMS-2154129.
Research supported by NSF Award DMS-2103154.
Research partially supported by NSF Awards DMS-1952767 and DMS-2153576.
Research supported by an NSF CAREER Award and by NSF Awards DMS-1952786 and DMS-2246847.
Research supported by NSF Award DMS-1800332.
Additional details
Related works
- Is new version of
- Discussion Paper: arXiv:2405.03455 (arXiv)
Funding
- National Science Foundation
- DMS-2054452
- National Science Foundation
- DMS-2348859
- National Science Foundation
- DMS-2154129
- National Science Foundation
- DMS-2103154
- National Science Foundation
- DMS-1952767
- National Science Foundation
- DMS-2153576
- National Science Foundation
- DMS-1952786
- National Science Foundation
- DMS-2246847
- National Science Foundation
- DMS-1800332
Dates
- Accepted
-
2025-08-20
- Available
-
2025-08-26Available online
- Available
-
2025-08-28Version of record