ABSTRACT
Paul Erdős and George Szekeres rediscovered Ramsey’s theorem while looking for a solution to the Happy End Problem, i.e., the problem of finding vertices of a convex n-gon in a given set of points in the plane.
This chapter provides details about several classical results related to the Happy End Problem and briefly summarizes the Problem’s 90-year history.
The chapter starts with a section that discusses the problem of finding vertices of a convex quadrilateral and a convex pentagon. The latter case is discussed in detail. The second section provides a solution to the general case. The fact that, for any natural number n, there is a threshold after which any set of points in general position contains vertices of a convex n-gon is proven in two ways, via Ramsey’s theorem and via theorem on cups and caps. The following section establishes upper and lower bound for the threshold and justifies Erdoős-Szekeres’ conjecture that, for a given n, the threshold is 2n−2 + 1.
The fourth section briefly summarizes the current state of Erdoős-Szekeres’ conjecture. The last section includes exercises related to various combinatorial problems in the plane.
