## You are here

Homehappy ending problem

## Primary tabs

# happy ending problem

The happy ending problem 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 [6] 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

- 1 F. R. K. Chung and R. L. Graham, Forced convex $n$-gons in the plane, Discrete Comput. Geom. 19 (1996), 229–233.
- 2 P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470.
- 3 P. Erdős and G. Szekeres, On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest Eötvös Sect. Math. 3–4 (1961), 53–62.
- 4 D. Kleitman and L. Pachter, Finding convex sets among points in the plane, Discrete Comput. Geom. 19 (1998), 405–410.
- 5 W. Morris and V. Soltan, The Erdős-Szekeres problem on points in convex position – a survey, Bull. Amer. Math. Soc. 37 (2000), 437–458.
- 6 L. Peters and G. Szekeres, Computer solution to the 17-point Erdős-Szekeres problem, ANZIAM J. 48 (2006), 151–164.
- 7 G. Tóth and P. Valtr, Note on the Erdős-Szekeres theorem, Discrete Comput. Geom. 19 (1998), 457–459.
- 8 G. Tóth and P. Valtr, The Erdős-Szekeres theorem: upper bounds and related results. Appearing in J. E. Goodman, J. Pach, and E. Welzl, eds., Combinatorial and computational geometry, Mathematical Sciences Research Institute Publications 52 (2005) 557–568.

## Mathematics Subject Classification

51D20*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Comments

## Pictures in PlanetMath

I didn't mean to sit on PrimeFan's correction for a whole month, but these things came up in my life and I was always forgetting stuff for like the past month, etc. I imagine there is some document somewhere on this website that explains how to put in pictures. I just have no idea where it's at, and so I have no idea how to put pictures on PlanetMath either. I think the entry on Gauss has a bitmap picture of him, but for something like a diagram is there some kind of vector thingie I could use?

## Re: Pictures in PlanetMath

Maybe there's a better way, but I've always created a JPEG of the graphics and included it using \includegraphics{foo.jpg}. I've never done this in PlanetMath, only in my own documents, so I have no idea if it works here.

I did spend some time on the web investigating how to do this, and all other methods seem to be even more klunky or difficult.

## Re: Pictures in PlanetMath

For the type of picture you'd want for this article, I would recommend a program like Ipe. It's a GPLed vector drawing program available for several systems that plays nice with LaTeX. Consult http://ipe.compgeom.org for more details.

## Re: Pictures in PlanetMath

> I imagine

> there is some document somewhere on this website that

> explains how to put in pictures. I just have no idea where

> it's at, and so I have no idea how to put pictures on

> PlanetMath either.

It is in the documentation section, alongside the

other site documents:

http://planetmath.org/?op=getobj&from=collab&id=53

## Re: Pictures in PlanetMath

Oh thank you very much for that link! That's precisely what I need to read! Thank you!

## Re: Pictures in PlanetMath

I'll consider that after I read the PM guidelines rspuzio pointed out to me.