Speaker:
Andrew Suk
Speaker Link:
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)}.