# happy ending problem

The asks, for a given integer $n>2$, to find the smallest number $g(n)$ of points laid on a plane in general position such that a subset of $n$ points can be made the vertices of a convex $n$-agon.

It is obvious that for $n=3$, just three points in general position are sufficient to create a triangle  . For $n=4$, Paul Erdős and Esther Klein (later Szekeres) determined that at least five points are necessary, and Kalbfleisch later determined $g(5)=9$. Much later, George Szekeres (posthumously) and Lindsay Peters published a computer proof  that $g(6)=17$.

For higher $n$, Erdős and George Szekeres in 1935 gave the upper bound

 $g(n)\leq\binom{2n-4}{n-2}+1.$

Later, in 1961 they gave the lower bound $g(n)\geq 1+2^{n-2}$.

New ideas for the upper bound were in the air in the late 1990s, with Chung and Graham showing that if $n\geq 4$, then

 $g(n)\leq\binom{2n-4}{n-2},$

while Kleitman and Pachter showed that then

 $g(n)\leq\binom{2n-4}{n-2}+7-2n.$

And Géza Tóth and Pavel Valtr in 1998 gave the upper bound

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

which in 2005 they refined to

 $g(n)\leq\binom{2n-5}{n-3}+1.$

## References

Title happy ending problem HappyEndingProblem 2013-03-22 16:16:21 2013-03-22 16:16:21 PrimeFan (13766) PrimeFan (13766) 13 PrimeFan (13766) Definition msc 51D20 happy end problem