## The Erdős Szekeres polygon problem – Solved asymptotically by Andrew Suk.

Here is the abstract of a recent paper by Andrew Suk. (I heard about it from a Facebook post by Yufei Zhao. I added a link to the original Erdős Szekeres’s paper.)

Let ES(n) be the smallest integer such that any set of ES(n) points in the plane in general position contains n points in convex position. In their seminal 1935 paper, Erdős and Szekeres showed that

$ES(n)\le {{2n-4}\choose{n-2}}+1=4^{n-o(n)}$

In 1960, they showed that

$ES(n) \ge 2^{n-2}+1$,

and conjectured this to be optimal. Despite the efforts of many researchers, no improvement in the order of magnitude has ever been made on the upper bound over the last 81 years. In this paper, we nearly settle the Erdős-Szekeres conjecture by showing that

$ES(n)=2^{n+o(n)}$.

This is amazing! The proof uses a 2002 “positive-fraction” version of the Erdős-Szekeres theorem by Pór and Valtr.

Among the many beautiful results extending, applying, or inspired by the Erdős Szekeres theorem let me mention an impressive recent body of works on the number of points in $\mathbb R ^d$ which guarantee n points in cyclic position. A good place to read about it is the paper by Bárány, Matoušek and Pór Curves in $\mathbb R^d$  intersecting every hyperplane at most d+1 times, where references to earlier papers by Conlon, Eliàš,  Fox, Matoušek, Pach, Roldán-Pensado, Safernová, Sudakov, Suk, and others.

This entry was posted in Combinatorics, Geometry, Updates and tagged . Bookmark the permalink.

### 2 Responses to The Erdős Szekeres polygon problem – Solved asymptotically by Andrew Suk.

1. random says:

Congratulations for the result, and just a random (extremely pedantic) note: since the starting SZ in Szekeres is one letter/sound in Hungarian (not unlike the German “es-zett”), the notation would look better as ESz(n) …