Departmental Colloquium
Andrew Suk
UIC
On the Erdos-Szekeres convex polygon problem
Abstract: 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)}.
Tea at 4:15 in SEO 300
Friday November 11, 2016 at 3:00 PM in SEO 636