Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Im giving a small talk for a combinatorics class on the Erdos-Szekeres conjecture regarding the happy ending problem (the paper is focused on recent work regarding the conjecture). I always find that when the audience is not up for a long technical proof, and they aren't familiar with the field (in this case combinatorial geometry) that it is important to provide strong motivation for why the problem is important, and perhaps mention a couple interesting related results that have applications in other fields, or to other problems.

For the Happy Ending problem, I am aware of connections to the $n$-hole problem for points in general position, Ramsey theory (via the original paper by erdos and szekeres in 1935), and the generalization of the E&S theorem for convex bodies. But Im not sure if these are good things to mention since the class does not know any Ramsey theory and convex bodies are probably too abstract to mention offhand.

So my question is: does anyone know of other interesting related results to the Happy Ending Problem, and the corresponding theorem and conjecture. Or, can you tell me succinctly why or why not this conjecture is important in mathematics.

I will accept anything along the lines of similar geometrically or combinatorially, directly related, or mentioned in a paper involving the E&S conjecture.

The original paper from 1935 is a goldmine of things like the ordered pigeonhole principle, but Im interested in things I havent read yet.

share|cite|improve this question
Maybe if you just simply told the story of why its called the Happy Ending problem, people would be interested in it. It was the cause of two people getting married right? Either way I'm sure if you do lecture on it, someone will ask why its called that. – Eric Haengel Nov 5 '10 at 8:05
@Eric yes, Im sure I will bring that up. It doesnt provide any mathematical motivation, but Im sure it will help the talk be entertaining. – AnonymousCoward Nov 5 '10 at 18:51
up vote 4 down vote accepted

You might look at this for some recent related work, and investigate its 14 references: "Every Large Point Set contains Many Collinear Points or an Empty Pentagon." CCCG 2009, 99-102. The main result is exactly what is stated in the title.

share|cite|improve this answer
Thank you for this. This paper also references a couple interesting papers I have not read yet. – AnonymousCoward Nov 5 '10 at 18:50
You're welcome! – Joseph O'Rourke Nov 5 '10 at 20:35
This nice paper (Happy Endings for Flip Graphs) of David Eppstein mentions a version of the paper above in its references as well as showing other interesting connections with "flip graphs." – Joseph Malkevitch Nov 6 '10 at 0:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.