Speaker: 

Andrew Suk

Institution: 

UCSD

Time: 

Thursday, December 7, 2017 - 4:00pm to 5:00pm

Host: 

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)}.