Erdös-Szekeres conjecture

Importance: High ✭✭✭
Subject: Geometry
Recomm. for undergrads: no
Prize: $1000 (Erdös-Graham)
Posted by: mdevos
on: October 8th, 2008

\begin{conjecture} Every set of $2^{n-2} + 1$ points in the plane in general position contains a subset of $n$ points which form a convex $n$-gon. \end{conjecture}

This is one of the most famous unsolved problems in combinatorial geometry, perhaps due in part to its lovely history. The problem of showing that every sufficiently large set of points in general position determine a convex $n$-gon was the original inspiration of Esther Klein. Erdös called this the \Def{Happy end problem} since it led to the marriage of Esther Klein and George Szekeres. This problem was also one of the original sources of Ramsey Theory.

Let $f(n)$ denote the smallest integer so that every set of $f(n)$ points in the plane in general position contains $n$ points which form a convex $n$-gon. The fact that $f(n)$ exists for every $n$ was first established in a seminal paper of Erdös and Szekeres who proved the following bounds on $f(n)$. \[ 2^{n-2} + 1 \le f(n) \le { 2n-4 \choose n-2 } + 1 \]

The lower bound is conjectured to be the truth, and this is known to hold for $n \le 5$. A handful of recent papers on this problem have improved the upper bound to \[ f(n) \le {2n-5 \choose n-3} + 1. \]


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

* indicates original appearance(s) of problem.

Now true for n = 6 as well

Now true for n = 6 as well by computer-aided solution of Szekeres and Peters (2006).

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.