On the Erdos-Szekeres convex polygon problem

Printer-friendly version
Speaker: 
Andrew Suk
Institution: 
UCSD
Time: 
Thu, 12/07/2017 - 4:00pm - 5:00pm
Host: 
Nathan Kaplan
Location: 
RH 306

The classic 1935 paper of Erdos and Szekeres entitled "A combinatorial problem in geometry" was a starting point of a very rich discipline within combinatorics: Ramsey theory.  In that paper, Erdos and Szekeres studied the following geometric problem.  For every integer n ≥ 3, determine the smallest integer ES(n) such that any set of ES(n) points in the plane in general position contains n members in convex position, that is, n points that form the vertex set of a convex polygon.  Their main result showed that ES(n) ≤ {2n  - 4 \choose n-2} + 1 = 4^{n -o(n)}.  In 1960, they showed that ES(n) ≥ 2^{n-2} + 1 and conjectured this to be optimal.  In this talk, we will sketch a proof showing that ES(n) =2^{n +o(n)}.