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

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.

 

ES

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) …

  2. Pingback: More Math from Facebook | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s