Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Colloquium

Andrew Suk

University of Illinois, Chicago

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

Host: Sam Buss

December 1, 2016

10:00 AM

AP&M 6402

****************************