A Puzzle of Clever Connections Nears a Happy End

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 4ⁿ 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.

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.)

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.”)

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 4ⁿ 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 4ⁿ. 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.

“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.