Happy End Problem

 

The happy end problem, also called the "happy ending problem," is the problem of determining for  the smallest number of points  in general position in the plane (i.e., no three of which are collinear), such that every possible arrangement of  points will always contain at least one set of  points that are the vertices of a convex polygon of  sides. The problem was so-named by Erdős when two investigators who first worked on the problem, Ester Klein and George Szekeres, became engaged and subsequently married (Hoffman 1998, p. 76).

Since three noncollinear points always determine a triangle, .

Random arrangements of  points are illustrated above. Note that no convex quadrilaterals are possible for the arrangements shown in the fifth and eighth figures above, so  must be greater than 4. E. Klein proved that  by showing that any arrangement of five points must fall into one of the three cases (left top figure; Hoffman 1998, pp. 75-76).

Random arrangements of  points are illustrated above. Note that no convex pentagons are possible for the arrangement shown in the fifth figure above, so  must be greater than 8. E. Makai proved  after demonstrating that a counterexample could be found for eight points (right top figure; Hoffman 1998, pp. 75-76).

As the number of points  increases, the number of -subsets of  that must be examined to see if they form convex -gons increases as , so combinatorial explosion prevents cases much bigger than  from being easily studied. Furthermore, the parameter space become so large that searching for a counterexample at random even for the case  with  points takes an extremely long time. For these reasons, the general problem remains open.

 was demonstrated by Szekeres and Peters (2006) using a computer search which eliminated all possible configurations of 17 points which lacked convex hexagons while examining only a tiny fraction of all configurations.

Erdős and Szekeres (1935) showed that  always exists and derived the bound

(1)

where  is a binomial coefficient. For , this has since been reduced to  for

(2)

by Chung and Graham (1998),  for

(3)

by Kleitman and Pachter (1998), and  for

(4)

by Tóth and Valtr (1998). For , these bounds give 71, 70, 65, and 37, respectively (Hoffman 1998, p. 78).

The values of  for , 7, ... are 37, 128, 464, 1718, ... (OEIS A052473).

---

REFERENCES

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, p. 78, 2003.

Chung, F. R. K. and Graham, R. L. "Forced Convex -gons in the Plane." Discr. Comput. Geom. 19, 367-371, 1998.

Erdős, P. and Szekeres, G. "A Combinatorial Problem in Geometry." Compositio Math. 2, 463-470, 1935.

Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, pp. 75-78, 1998.

Kleitman, D. and Pachter, L. "Finding Convex Sets among Points in the Plane." Discr. Comput. Geom. 19, 405-410, 1998.

Lovász, L.; Pelikán, J.; and Vesztergombi, K. Discrete Mathematics, Elementary and Beyond. New York: Springer-Verlag, 2003.

Sloane, N. J. A. Sequence A052473 in "The On-Line Encyclopedia of Integer Sequences."Szekeres, G. and Peters, L. "Computer Solution to the 17-Point Erdős-Szekeres Problem." ANZIAM J. 48, 151-164, 2006.

Tóth, G. and Valtr, P. "Note on the Erdős-Szekeres Theorem." Discr. Comput. Geom. 19, 457-459, 199

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength