Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

Request Permissions   Purchase Content 
 

 

On the Erdős-Szekeres convex polygon problem


Author: Andrew Suk
Journal: J. Amer. Math. Soc.
MSC (2010): Primary 52C10; Secondary 05D10
DOI: https://doi.org/10.1090/jams/869
Published electronically: September 30, 2016
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ ES(n)$ be the smallest integer such that any set of $ ES(n)$ points in the plane in general position contains $ n$ points in convex position. In their seminal 1935 paper, Erdős and Szekeres showed that $ ES(n) \leq {2n - 4\choose n-2} + 1 = 4^{n -o(n)}$. In 1960, they showed that $ ES(n) \geq 2^{n-2} + 1$ and conjectured this to be optimal. In this paper, we nearly settle the Erdős-Szekeres conjecture by showing that $ ES(n) =2^{n +o(n)}$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 52C10, 05D10

Retrieve articles in all journals with MSC (2010): 52C10, 05D10


Additional Information

Andrew Suk
Affiliation: University of Illinois, Chicago, Illinois 60607
Email: suk@uic.edu

DOI: https://doi.org/10.1090/jams/869
Received by editor(s): May 3, 2016
Received by editor(s) in revised form: August 26, 2016
Published electronically: September 30, 2016
Additional Notes: The author is supported by NSF grant DMS-1500153.
Article copyright: © Copyright 2016 American Mathematical Society