Title: On the Erdos-Szekeres Convex Polygon Rroblem
Speaker: Andrew Suk, University of Illinois at Chicago
Date: Monday, December 12, 2016 2:00 pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
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 - 4choose 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)}.