combinatorics

A Puzzle of Clever Connections Nears a Happy End

The three young friends who devised the “happy ending” problem became some of the most influential mathematicians of the 20th century, but were never able to solve their own puzzle. Now it receives its first big breakthrough.

Olena Shmahalo/Quanta Magazine

One measure of a good math problem is that, in trying to solve it, you will make some unexpected discoveries. Such was Esther Klein’s experience in 1933.

At the time, Klein was 23 years old and living in her hometown of Budapest, Hungary. One day she brought a puzzle to two of her friends, Paul Erdős and George Szekeres: Given five points, and assuming no three fall exactly on a line, prove that it is always possible to form a convex quadrilateral — a four-sided shape that’s never indented (meaning that, as you travel around it, you make either all left turns or all right turns).

In 1933 Esther Klein shared a puzzle with two young friends, Paul Erdős and George Szekeres: Given five points, and assuming no three are on a line, prove that it’s always possible to connect four of them to form a convex polygon.

Erdős and Szekeres eventually found a way to show that Klein’s statement was true (she had worked out the proof before bringing it to them), and it got them thinking: If five points are enough to guarantee that you can always connect four to form this kind of quadrilateral, how many points are needed to guarantee that you can form this same kind of shape with five sides, or 11 sides, or any number of sides?

By 1935 Erdős and Szekeres had solved this problem for shapes with three, four and five sides.  They knew it took three points to guarantee you could construct a convex triangle, five points to guarantee a convex quadrilateral, and nine points to guarantee a convex pentagon.

In the same paper in which they presented these solutions, Erdős and Szekeres proposed an exact formula for the number of points it would take to guarantee a convex polygon of any number of sides: 2(n–2) + 1, where n is the number of sides. But their proposal was just that — a well-aimed conjecture. Erdős, as he did with many problems, offered a cash bounty of $500 to anyone who could prove the formula was correct.

The puzzle was given a memorable nickname, the “happy ending” problem (or “happy end” problem as originally dubbed by Erdős), for reasons that had nothing to do with math. Instead, it reflected the primary nonmathematical consequence of their discussion of points, lines and shapes: Esther Klein and George Szekeres fell in love and married on June 13, 1937.

Esther Klein in 1927, George Szekeres in 1928 and Paul Erdős in an undated photograph.

Esther Klein in 1927, George Szekeres in 1928 and Paul Erdős in an undated photograph.

Photos Courtesy of KöMaL (Klein, Szekeres); Photo Courtesy of Ronald Graham (Erdős)

Yet as the decades passed, mathematicians made virtually no progress in proving the conjecture. (The only other shape whose result is known is a hexagon, which requires at least 17 points, as proved by Szekeres and Lindsay Peters in 2006.) Now, in work recently published in the Journal of the American Mathematical Society, Andrew Suk of the University of Illinois, Chicago, provides nearly decisive evidence that the intuition that guided Erdős and Szekeres more than 80 years ago was correct.

Split Shapes

At a very general level, the happy ending problem is about finding ways to add sides to a polygon. Say you have five points. You know that this is enough to guarantee that you can construct a convex quadrilateral by connecting four of those points. From there, you want to increase the number of sides of that polygon — from four sides to five, six and beyond. As you do this, you need to keep track of the number of points you need to add in order to guarantee that you can make the desired shape.

Erdős and Szekeres were not able to prove their formula, but they had a clear sense of the path a mathematician might follow to get there. In the 1935 paper where they made the conjecture, they wrote about how convex polygons can be thought of as what are now called “cups” and “caps” glued together. A cup is made from a set of points in a “u” shape. It forms the bottom part of the polygon. A cap is a set of points in an “n” shape that forms the top.

The advantage of thinking about a polygon as a cup and cap glued together is that it’s easier to think about how you’d enlarge a cup or a cap than it is to figure out how to enlarge a polygon. If you have five points forming a convex cap, for instance, you can always enlarge it by adding a sixth point off one end or the other. But with a convex five-sided polygon, it’s less obvious how you’d add a sixth point while still preserving its convexity.

“They’re just a little easier to deal with,” said Ronald Graham, a mathematician at the University of California, San Diego, and a longtime friend of Erdős’s. “Say you have a cap. Depending on where you put one more point, it can still form a cap. You can kind of see where it’s going to be. If you have a convex polygon and you add one more point, you don’t have quite as much control about what’s going on.”

In their 1935 paper Erdős and Szekeres proved what’s called the cups-caps theorem, which tells you the minimum number of points you need before you’re guaranteed either a cup or a cap of a certain size. The cups-caps theorem also creates an upper bound on the happy ending problem for reasons that are intuitive enough: If you have a cup, you can always create a convex polygon simply by drawing a line between the cup’s endpoints. It’s not the most efficient way to construct a convex polygon, but it guarantees you can make one.

Using the cups-caps theorem, Erdős and Szekeres proved that if you have 4n points, you can always find a cup or a cap that gives you an n-sided convex polygon. This value is exponentially larger than the conjectured number of points, 2(n–2) + 1, which makes it kind of unsatisfying once n gets large — like buying a pound of parsley when you really just need a pinch.

Erdős and Szekeres understood that if they could find a more efficient way to combine a cup with a cap, they could prove that their conjectured value was correct. The problem they ran into was that you can’t always glue cups and caps together to form a convex polygon. For the gluing to work, the cap needs to be “strictly above” the cup, as mathematicians put it. There’s an exact way of defining what this condition means: A line drawn through any two points in the cap lies above all the points in the cup. When it’s not present — when the cup is not strictly above the cap — the shape you get when you glue them together is not convex.

This cups-caps impasse held for many years: Mathematicians viewed the gluing of cups and caps as the best way to approach the problem but couldn’t figure out how to do it. They wanted to find a large cup and a large cap that were in the right position with respect to each other, such that when they were glued together, you would get the biggest convex polygon you could be guaranteed (given the total number of points you started with). Yet in order to prove that their caps were always strictly above their cups (or their cups were strictly below their caps), they always ended up having to restrict the cup size and cap size to a degree that undermined the whole approach.

“They’ll be so small that what you gain by putting a cap and a cup together doesn’t help you much. You lose more than what you gain,” said Gábor Tardos, a mathematician at the Alfréd Rényi Institute of Mathematics of the Hungarian Academy of Sciences in Budapest. “That was the obstacle.”

It was, until Andrew Suk found a way over it.

Sorting Spikes

Suk’s work focuses on an area of mathematics called Ramsey theory, which is about as old as the happy ending problem itself. Ramsey theory says, broadly, that within large disorganized sets — like a set of points dispersed randomly on a plane — you will always be able to find well-organized subsets. This basic idea was first discovered mathematically a few years before Klein posed her problem to Erdős and Szekeres, and it was rediscovered by the two men themselves in the course of studying the happy ending problem.

When applied to this problem, Ramsey theory states that no matter how you place your points on the plane, when the number of points grows sufficiently large, you’re guaranteed to get a well-organized subset of points that can be joined to form a convex n-gon. There’s absolutely no way to avoid it.

The mathematician Andrew Suk has used tools from Ramsey theory to get close to proving the 82-year-old “happy ending” conjecture, which states that a convex polygon with n sides can always be formed if you have at least 2(n–2) + 1 points. 
1. Suk starts with a large number of points. 2. He then divides the points into subsets called “spikes” that are arrayed around a convex “hull.” Spike
Hull

3. Suk finds structured sets of points within each spike: either chains (blue), which run approximately perpendicular to the hull, or antichains (red), which run parallel to it.
 Antichain Chain 4. He uses Ramsey theory to show that points from every possible arrangement of chains and antichains can always be combined in some way to make an n-sided polygon. Selected antichains 10-sided convex polygon

Suk uses an idea from Ramsey theory to divide up the points into subsets that are all in convex position with respect to each other. Ramsey theory tells him how many of these subsets he can create and roughly how many points have to be in each. Now each subset is contained within a triangular “spike” and all the spikes are arrayed around the outside of what you can picture as a convex hull. The graphic below shows what it might look like. (Note: During this step, and the subsequent steps, Suk doesn’t ever move points around; he just focuses on structured subsets of points that were present from the start.)

The mathematician Andrew Suk has used tools from Ramsey theory to get close to proving the 82-year-old “happy ending” conjecture, which states that a convex polygon with n sides can always be formed if you have at least 2(n–2) + 1 points. 
1. Suk starts with a large number of points. 2. He then divides the points into subsets called “spikes” that are arrayed around a convex “hull.” Spike
Hull

3. Suk finds structured sets of points within each spike: either chains (blue), which run approximately perpendicular to the hull, or antichains (red), which run parallel to it.
 Antichain Chain 4. He uses Ramsey theory to show that points from every possible arrangement of chains and antichains can always be combined in some way to make an n-sided polygon. Selected antichains 10-sided convex polygon

After organizing the original points into spikes, Suk begins to reason about subsets within each spike. His goal is to prove that within each spike he’s guaranteed either a cup or a cap of a certain size. And because the spikes are all in convex position with respect to each other, he knows that cups or caps within one spike can be combined with cups or caps within other spikes.

To hunt for cups and caps, Suk uses another part of Ramsey theory called Dilworth’s theorem to organize the points in each spike. Dilworth’s theorem implies that inside each spike there’s a set of some guaranteed minimum size in which the points are either parallel or perpendicular to the convex hull the spikes are organized around. (In this figure, the blue dots are perpendicular “chains” and the red dots are parallel “antichains.”)

The mathematician Andrew Suk has used tools from Ramsey theory to get close to proving the 82-year-old “happy ending” conjecture, which states that a convex polygon with n sides can always be formed if you have at least 2(n–2) + 1 points. 
1. Suk starts with a large number of points. 2. He then divides the points into subsets called “spikes” that are arrayed around a convex “hull.” Spike
Hull

3. Suk finds structured sets of points within each spike: either chains (blue), which run approximately perpendicular to the hull, or antichains (red), which run parallel to it.
 Antichain Chain 4. He uses Ramsey theory to show that points from every possible arrangement of chains and antichains can always be combined in some way to make an n-sided polygon. Selected antichains 10-sided convex polygon

From here, Suk builds cups and caps by going around the figure and combining points from different spikes. Based on another argument from Ramsey theory — the pigeonhole principle — Suk is able to show that the arrangement of chains and antichains around the convex hull must fall into one of two configurations.

The first possibility is that he finds many red antichains. In this case, Suk argues that if one of the antichains contains an n-cup, then he’s finished, as he’s found the n-gon he’s looking for. Otherwise, the cups-caps theorem implies that there have to be mini-caps inside each of the antichains that can be combined to form one large, convex n-cap — again, giving him the shape he’s looking for.

The second scenario is thornier. In this case, he finds many consecutive spikes with blue perpendicular chains. Here, Suk moves left to right around the spikes. At each step he reasons about whether cups and caps can be combined to form a convex n-gon. If the answer is no at every step, he’s in the very worst-case scenario. But even there, Suk shows that as a consequence of the preceding futility, the last spike must contain an n-element cap all by itself.

“I keep applying this argument over and over such that by the time I get to the last region, I have to get it,” Suk said.

Suk uses tools from Ramsey theory to think about the kinds of organized substructures that have to emerge, and how large those substructures have to be, and how one kind of structure interacts with another. As a result, he’s able to assess whole categories of configurations in a small number of moves, cornering the points into their most difficult arrangements, and proving that even there, they have to yield the convex n-gon he’s looking for.

Almost Ended

Suk’s work suggests that Erdős and Szekeres’ conjecture is almost certainly true, even if he stops short of proving it completely. Suk’s proof brings the previous upper bound on the problem — about 4n points — down to a value that’s almost equal to the formula proposed by Erdős and Szekeres when the number of points is large.

“I think no one would have been shocked until now to see if the truth is close to 4n. Now we definitely know the conjecture is roughly true, which of course makes it more believable that it is actually true for every n,” said János Pach, a prominent figure in combinatorics at the Swiss Federal Institute of Technology of Lausanne and Suk’s adviser during his graduate studies at New York University.

Even when there’s a consensus about whether a long-standing conjecture is true or not, often it takes the advent of some complicated new mathematical machinery to settle it one way or the other. That was not the case here, where the basic path Suk followed, of combing cups and caps, was evident from the start.

 

Esther Klein (third from left), Paul Erdős and George Szekeres visiting the University of Newcastle, Australia, in 1984.

Esther Klein (third from left), Paul Erdős and George Szekeres visiting the University of Newcastle, Australia, in 1984.

©The University of Newcastle; UON Photographer

“It’s very clever, very elementary, something Erdős and Szekeres could have done themselves,” Graham said. Pach adds, “I think Erdős and Szekeres would be extremely happy to see they were actually on the right track and these ideas they came up with can be made to work.”

Neither is alive today. Erdős passed away in 1996, though he lives on in the many cash prizes he endowed, which are now managed mostly by Graham. Szekeres outlived Erdős by nearly a decade. He and Klein were both in their mid-nineties when they moved into a nursing home in Adelaide, Australia, in 2005. They died there on August 28, 2005, within an hour of each other — 70 years after the birth of the happy ending problem, and approximately a decade before it was nearly settled.

Comment on this article