On the Erdos-Szekeres convex polygon problem

School of Mathematics Colloquium
Thursday, November 17, 2016 - 11:05
1 hour (actually 50 minutes)
Skiles 006
University of Illinois at Chicago
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 \geq 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) \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.  Despite the efforts of many researchers, no improvement in the order of magnitude has been made on the upper bound over the last 81 years. In this talk, we will sketch a proof showing that ES(n) =2^{n +o(n)}.