Home » Subject » Geometry

Erdös-Szekeres conjecture

Importance: High ✭✭✭
Author(s): Erdos, Paul
Szekeres, George
Subject: Geometry
Keywords: combinatorial geometry
Convex Polygons
ramsey theory
Recomm. for undergrads: no
Prize: $1000 (Erdös-Graham)
Posted by: mdevos
on: October 8th, 2008
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.

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 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. \]

Bibliography



* indicates original appearance(s) of problem.
add new comment

Now true for n = 6 as well

On April 14th, 2009 Anonymous says:

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

reply

Comment viewing options

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