Happy ending problem

The Happy Ending problem (so named by Paul Erdős since it led to the marriage of George Szekeres and Esther Klein) is the following statement:

Theorem. Given five points in the plane in general position, it is possible to select four of them that form a convex quadrilateral.

Erdős and Szekeres (1935) proved the following generalisation:

Theorem. Given a positive integer N, there exists a positive integer M such that among any M points in the plane in general position, it is possible to select N of them that form a convex N-gon.

Denoting by f(N) the minimal possible M for which the conclusion holds, it is known that

• f(3) = 3. This is trivial.
• f(4) = 5. This was the original problem, proved by Esther Klein.
• f(5) = 9. According to Erdős and Szekeres (1935), this was first proved by E. Makai; the first published proof appeared in Kalbfleisch et al (1970).
• f(6) = 17. This has been proved by George Szekeres and Lindsay Peters in work yet to be published. They carried out an exhaustive computer search, essentially examining every possible configuration of 17 points to verify that six of them form a convex hexagon. It is remarkable that Szekeres was writing computer code in Fortran in his mid-nineties to carry out such a project.
• The value of f(N) is unknown for all N > 6; by the Erdős-Szekeres theorem it is known to be finite.

On the basis of the known values of f(N) for N = 3, 4 and 5, Erdős and Szekeres conjectured in their original paper that

$f(N)=1+2^{N-2}\quad {\mbox{for all }}N\geq 3.$

They proved later (Erdős and Szekeres, 1961), by constructing explicit examples, that

$f(N)\geq 1+2^{N-2},$

but the best known upper bound is only

$f(N)\leq {2n-5 \choose n-3}+2,$

due to Tóth and Valtr (1998) (see binomial coefficient).

See also

• Ramsey theory

References

• Erdős, P., Szekeres, G., A combinatorial problem in geometry, Compositio Math. 2 (1935), 463--470.
• Erdőos P., Szekeres G., On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 3-4 (1961), 53–62. Reprinted in: Paul Erdős: The Art of Counting. Selected Writings (J. Spencer, ed.), pp. 680–689, MIT Press, Cambridge, MA, 1973.
• Kalbfleisch J.D., Kalbfleisch J.G., Stanton R.G., A combinatorial problem on convex regions, Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, La, 1970. Congr. Numer. 1 (1970), 180-188.
• Morris, W., and V. Soltan. 2000. The Erdös-Szekeres problem on points in convex position--A survey. Bulletin of the American Mathematical Society 37(October): 437.
• Tóth G., Valtr P., Note on the Erdős-Szekeres theorem, Discrete Comput. Geom. 19 (1998), 457–459.

External links

• http://www.maa.org/mathland/mathtrek_10_3_00.html