Nearly every Sunday during the winter of 1933 in Budapest, a small group of students would meet somewhere in the city at a park or cafe to discuss mathematics. The gathering typically included Paul Erdös (1913–1996), who was attending the University of Budapest, György (George) Szekeres, a recent chemical engineering graduate of the Technical University of Budapest, and another student, Esther Klein.
In addition to feeding their passion for mathematics, the students enjoyed exchanging personal gossip and talking politics. In a way, they had their own, informal university without walls, and they relished the chance to explore new ideas.
On one particular occasion, Klein challenged the group to solve a curious problem in plane geometry that she had recently encountered. Suppose there are five points positioned anywhere on a flat surface, as long as no three of the points form a straight line. When four points are joined, they form a quadrilateral–a four-sided figure. Klein had noticed that given five points, four of them always appeared to define a convex quadrilateral. The term convex means that the figure has no indentations. Thus, a square is convex, but a crescent quadrilateral (an angular boomerang or arrowhead shape with four vertices) is not.
Here, ACDE is a convex quadrilateral, but ABCE (shaded) is not because of the indentation at B. |
Klein asked if anyone could prove that a convex quadrilateral has to be present in any given set of five points lying in a plane, with no three points in a line. After letting her friends ponder the problem, Klein explained her proof.
She reasoned that there are three different ways in which a convex polygon encloses all five points. You can imagine the points as nails sticking out of a board with an elastic band stretched so that it rings the largest possible number of nails.
The simplest case occurs when a convex polygon results from joining four points to create a quadrilateral, which fences in the remaining point and automatically satisfies the requirement.
In the second case, if the convex polygon is a pentagon incorporating all five points, then any four of these points can be connected to form a quadrilateral.
Finally, if the convex polygon includes just three points to create a triangle, the two points left inside the triangle define a line that splits the triangle so that two of the triangle’s points are on one side of the line. These two points plus the two interior points automatically form a convex quadrilateral.
Inspired by Klein’s argument, Szekeres went on to generalize the result, proving that among points randomly scattered across a flat surface, you can always find a set that forms a particular polygon–if there are enough points. For example, you can always find a convex pentagon in an array of nine points but not among just eight points.
Szekeres and Erdös then proposed that if the number of points that lie in a plane is 1 + 2k-2, you can always select k points so that they form a convex polygon with k sides. Thus, for a quadrilateral, k is 4, and the number of points required will be 1 + 24-2 = 1 + 22 = 5. For a convex pentagon, k is 5, and the number of points required will be 9.
In describing this occasion in a memoir written many years later, Szekeres recalled: “We soon realized that a simple-minded argument would not do and there was a feeling of excitement that a new type of geometrical problem [had] emerged from our circle which we were only too eager to solve.”
Erdös dubbed it the “happy end” problem. The ending he had in mind was the subsequent marriage of Szekeres and Klein, who now live in Sydney, Australia.
Interestingly, no one has yet proved the conjecture concerning the precise number of points required to guarantee the presence of a convex polygon. Indeed, the problem is solved only for the values k = 3, 4 (due to Klein), and 5. So, no one has even demonstrated that any set of 17 points in the plane always contains six points that are the vertices of a convex hexagon.
In the October Bulletin of the American Mathematical Society, Walter D. Morris and Valeriu Soltan of George Mason University in Fairfax, Va., survey known results and open questions related to the original conjecture proposed by Erdös and Szekeres.
Expressed mathematically, the problem asks: For any integer n greater than or equal to 3, determine the smallest positive integer N(n) such that any set of at least N(n) points in general position in the plane (that is, no three of the points are on a line) contains n points that are the vertices of a convex n-gon.
“Despite the efforts of many mathematicians, the Erdös-Szekeres problem is still far from being solved,” Morris and Soltan note.
At the same time, the unsolved problem has suggested a wide variety of related questions worthy of exploration. Some mathematicians have looked for other types of patterns among sets of points, and others have generalized the question to higher dimensions and other situations.
That’s the rich legacy of an elegant problem first suggested nearly 70 years ago and still attracting mathematical attention.
