Open Problem Garden

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.

1 comment

Open Problem Garden

Bibliography

Reply

Navigate

Recent Activity