|Ivars Peterson's MathTrek|
October 2, 2000
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.
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.
Copyright 2000 by Ivars Peterson
Graham, R.L., and J.H. Spencer. 1990. Ramsey theory. Scientific American (July):112.
Hoffman, P. 1998. The Man Who Loved Only Numbers: The Story of Paul Erdös and the Search for Mathematical Truth. New York: Hyperion.
Morris, W., and V. Soltan. 2000. The Erdös-Szekeres problem on points in convex position--A survey. Bulletin of the American Mathematical Society 37(October):437. See http://www.ams.org/journal-getitem?pii=S0273-0979-00-00877-6.
Peterson, I. 1999. Party games. MAA Online (Dec. 6).
______. 1998. The Jungles of Randomness: A Mathematical Safari. New York: Wiley.
______. 1996. Paul Erdös: An infinity of problems. MAA Online (Oct. 7).
______. 1996. Groups, graphs, and Paul Erdös. MAA Online (June 10).
______. 1993. Party numbers. Science News 144(July 17):46.
Schecter, B. 1998. My Brain is Open: The Mathematical Journeys of Paul Erdös. New York: Simon & Schuster.
You can find an explanation of the "happy end problem" with examples and references at http://mathworld.wolfram.com/HappyEndProblem.html.
Comments are welcome. Please send messages to Ivars Peterson at firstname.lastname@example.org.
Ivars Peterson is the mathematics/computer writer and online editor at Science News (http://www.sciencenews.org). He is the author of The Mathematical Tourist, Islands of Truth, Newton's Clock, Fatal Defect, and The Jungles of Randomness. He also writes for the children's magazine Muse (http://www.musemag.com) and is working on a book about math and art.
Ivars Peterson will present "A Kaleidoscope of Mathematics and Art" at the Joint Mathematics Meetings in New Orleans on Jan. 13, 2001, at 10:05 a.m.