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. The problem also turned out to be a application of a theorem developed by Frank Ramsey (see "Playing Fields of Logic")
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.
Erdős himself later played a central role in the transformation of Ramsey theory, which involves the application of Ramsey's theorem and related propositions, from a collection of isolated results into a coherent body of work,
Though pursued mainly for the thought-provoking mathematical puzzles that it suggests, Ramsey theory has begun to play a role in the design of vast computer and telephone networks. Techniques used in the theory can help engineers and computer scientists to take advantage of patterns that inevitably arise in large systems in which data storage, retrieval, and transmission have a significant component.
.
In the meantime, work has continued on 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. 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 many decades earlier and still attracting mathematical attention.
Previously: Playing Fields of Logic
No comments:
Post a Comment