Every crowd holds a bowl or a dome

The sequence that cannot avoid a staircase proved that any $mn + 1$ distinct numbers contain $m + 1$ that climb or $n + 1$ that fall, and mentioned, in passing, the question it came from: how many points in the plane, no three on a line, force $k$ of them to be the corners of a convex polygon? Esther Klein showed that five points force a convex quadrilateral, and Paul Erdős and George Szekeres proved in 1935 that for every $k$ some finite number suffices. Their proof went through a pair of objects this essay is about, and they are the natural next step up from climbing and falling numbers.

A cup is a chain of points, left to right, that bends upward at every point, like the bottom of a bowl. A cap is a chain that bends downward at every point, like the top of a dome. The figure below shows twelve random points with the longest cup and the longest cap among them, found by checking every chain: five points each.

Climbing and falling were about the order of heights. Cups and caps are about the order of slopes: a chain is a cup when each step is steeper than the one before, and a cap when each is shallower. The theorem for sequences was a statement about pairs of points. This one is a statement about triples, and it is where the subject stops being a pigeonhole argument and becomes Ramsey theory proper.

A bowl or a dome, whatever the points #

The theorem Erdős and Szekeres proved is this. Any $\binom{k+l-4}{k-2} + 1$ points with distinct $x$-coordinates, no three on a line, contain a cup of $k$ points or a cap of $l$ points.

With $k = l = 3$ the number is $\binom{2}{1} + 1 = 3$, which is trivially right: three points not on a line bend one way or the other, so they are a 3-cup or a 3-cap. With $k = l = 4$ it is $\binom{4}{2} + 1 = 7$. With $k = l = 5$ it is $\binom{6}{3} + 1 = 21$.

The figure’s twelve points escape a 6-cup and a 6-cap without difficulty, since the bound for that pair is $\binom{8}{4} + 1 = 71$. They do not escape a 5-cup or a 5-cap, though that is not what the bound for $(5, 5)$ says — twelve is below twenty-one — but what this particular set happens to contain. The theorem is about the worst arrangement, and random points are far from worst.

The proof is Pascal’s rule #

Write $f(k, l)$ for the smallest number of points that forces a $k$-cup or an $l$-cap. The proof shows that

$$f(k, l) \;\le\; f(k-1, l) + f(k, l-1) - 1,$$

which, with the starting values $f(k, 3) = k$ and $f(3, l) = l$, is exactly the rule that builds Pascal’s triangle — every entry the sum of the two above it. The binomial coefficient is not an accident of the answer; it is the shape of the argument.

The argument itself is short. Take a set of $f(k-1, l) + f(k, l-1) - 1$ points, and suppose it has no $l$-cap. Mark every point that is the right-hand end of some $(k-1)$-cup. The unmarked points have no $(k-1)$-cup ending among them and no $l$-cap, so there are fewer than $f(k-1, l)$ of them — and the marked points therefore number at least $f(k, l-1)$. Among the marked points there is, by definition of $f(k, l-1)$, either a $k$-cup, which finishes the proof, or an $(l-1)$-cap.

Take that cap’s leftmost point $p$. It is marked, so a $(k-1)$-cup ends at $p$. Now compare two slopes at $p$: the last step of the cup, arriving at $p$, and the first step of the cap, leaving it. If the step leaving is steeper, the cup continues through the cap’s next point and becomes a $k$-cup. If the step leaving is shallower, the cap extends backward through the cup’s previous point and becomes an $l$-cap. One of the two must happen, because two slopes are either in order or not. The two chains meet at $p$ and one of them always wins.

It is the same move as the counters in the sequence theorem — label each point by the longest chains ending there — with one difference that matters. There, a pair of labels was assigned to each point and the pigeonhole principle forced a collision. Here the labels are chains, and the collision is a meeting point where one chain’s slope has to be compared with another’s. That comparison of three points at once is what makes this a theorem about triples.

A set that escapes, built by the same rule #

The bound would be a curiosity if it were loose. It is not: for every $k$ and $l$ there is a set of exactly $\binom{k+l-4}{k-2}$ points with no $k$-cup and no $l$-cap, so one point fewer than the bound can always escape. The construction runs the recursion backward.

To build a set with no $k$-cup and no $l$-cap, take a set with no $(k-1)$-cup and no $l$-cap and put it at the lower left; take a set with no $k$-cup and no $(l-1)$-cap and put it far up and to the right; and flatten each so that every slope inside a block is small compared with the slopes between blocks. Then a cup can bend upward through the lower block and take one point of the upper — after the huge jump in slope, nothing inside the flat upper block is steeper — so it has at most $(k-2) + 1$ points. A cap can take one point of the lower block and then bend downward through the upper, so it has at most $1 + (l-2)$. Neither reaches its limit.

Both constructions are checked by the same search that found the hero’s chains: every chain is tried, the longest cup and cap are recorded, and they come out one short of forbidden. And every extra point dropped into the picture, at random, completes a forbidden chain. That is the exactness of the bound seen from both sides — the construction shows the number cannot be smaller, the recursion that it inverts shows it cannot be larger.

The flattening is what makes these pictures hard to read at their own scale, which is why the blocks are magnified. A flat block looks like a row of points at the scale of the whole, and the whole construction for $k = l = 5$, twenty points, looks like a staircase of rows. The structure is all in slopes too small to see.

From pairs to triples #

It is worth seeing exactly how far the subject has moved from the principle it started with. The sequence theorem colours each pair of positions by whether the later number is larger, and the pigeonhole principle, applied to a pair of counters at each position, forces a long run of one colour. That is Ramsey theory for pairs, with a very special colouring — one in which the colours are consistent along chains, since larger-than is transitive.

Cups and caps colour each triple of points by the way it turns. There is no counter to pigeonhole: a single point’s position in the order says nothing about which way the triples through it turn. What replaces the counters is the pair of longest chains ending at each point, and what replaces the pigeonhole collision is the slope comparison at a meeting point. The cost of moving from pairs to triples shows up in the bound: $mn + 1$ for sequences, a product, against a binomial coefficient for cups and caps, which grows like a sum of products.

And the sequence theorem is still here, one level down. Sort points by their $x$-coordinates and read off their heights, and the result is a sequence whose climbs and falls are chains of points going up and down to the right. Those are statements about pairs of points. Cups and caps ask the next question, about how the chains bend, and the answers to both are forced by the same kind of meeting-point argument, one on pairs and one on triples.

Four points decide convexity #

There is a reason the happy ending problem is about $k$ points at once and yet every figure here checks convexity four points at a time. A set of points is in convex position exactly when every four of them are — if some point lies inside the hull of others, it lies inside a triangle of three of them, by Carathéodory’s theorem, and those four points are not in convex position. So the pentagon search tries every five, and for each five, the hull; but the obstruction it finds is always a point inside a triangle.

That is why Esther Klein’s quadrilaterals were the right starting point. A convex $k$-gon is a set of $k$ points every four of which are convex quadrilaterals, and the question is how many points force such a set. Put that way, it is a Ramsey question about 4-point subsets with a very special colouring, and the cups-and-caps argument is the device that converts it into a question about triples, where the transitivity makes it tractable.

From bowls and domes to convex polygons #

A cup is in convex position — its points are the corners of a convex polygon, closed up by the chord from first to last — and so is a cap. So any set with $\binom{2k-4}{k-2} + 1$ points contains $k$ in convex position, and the happy ending problem has a finite answer, $N(k)$, bounded by that binomial coefficient.

The bound is far from the truth. For a quadrilateral it says $\binom{4}{2} + 1 = 7$ points, and five suffice. For a pentagon it says $21$, and the truth is nine.

Eight points can avoid a convex pentagon, and the figure is one such set, found by a seeded random search and then checked exhaustively. That nine points always contain one was proved in 1970 by a case analysis, and it agrees with the formula Erdős and Szekeres conjectured in 1935: $N(k) = 2^{k-2} + 1$. They also proved, in 1961, that the conjecture cannot be improved — they built $2^{k-2}$ points with no convex $k$-gon, stacking cup-and-cap sets along a large dome, so the formula is at least a lower bound for every $k$.

Eighty years between the two lines #

The conjecture sits between two numbers: $2^{k-2} + 1$ from the construction, and $\binom{2k-4}{k-2} + 1$ from cups and caps. The binomial grows like $4^k/\sqrt k$, the power of two like $2^k$, and for large $k$ the gap is exponential.

Every value known sits on the lower line. $N(6) = 17$ was settled by George Szekeres and Lindsay Peters with a computer search organised around exactly the cup-and-cap structure above, published in 2006, seventy-one years after the conjecture and the year after Szekeres died. For the upper bound, a series of improvements through the 1990s and 2000s shaved the binomial coefficient by factors that grew with $k$ without changing its exponential rate. Then in 2016 Andrew Suk proved $N(k) \le 2^{k + o(k)}$: the upper bound grows at the rate of the lower one, up to a factor smaller than any exponential. The two lines on the figure, which diverge like $2^k$, are now known to be within a subexponential factor of each other.

Suk’s proof uses cups and caps too, but not alone. It combines them with a theorem about ordered triples coloured by orientation — the Ramsey theory of three-point configurations — and with a way of cutting a point set into pieces that behave, from a distance, like single points. The cup-and-cap recursion is the part everyone uses; what changed in 2016 was how to avoid paying its full binomial price.

Random crowds are easy, worst crowds are not #

The hero’s twelve random points held a cup and a cap of five each. That is far more than the worst case allows twelve points to guarantee — the extremal constructions show that twelve points can hold no cup or cap longer than four — and the gap grows with the number of points.

For $n$ points dropped uniformly into a square, the largest subset in convex position has on the order of $n^{1/3}$ points, a result of Imre Bárány and colleagues around the year 2000. The guarantee is only logarithmic: about half of $\log_2 n$ corners from cups and caps alone, and about $\log_2 n$ by Suk’s theorem below. A random crowd of a million points typically contains a convex polygon with on the order of a hundred corners, while some crowds of a million contain none with more than twenty-one.

The same contrast between worst and typical is the subject of the longest climb of a shuffle, where it is sharper still: for sequences, Erdős and Szekeres guarantee a monotone run of $\sqrt n$, and a random shuffle almost always has one twice that long, in both directions at once. Extremal combinatorics finds the worst arrangement, and the worst arrangement is very special — here, a nest of flattened blocks that no random process would ever produce. That is the same lesson the party problem’s larger cases teach: the colourings that escape are rare, structured and hard to find.

Ramsey theory for triples #

The cups-and-caps theorem is worth placing in the family the party problem started. There, every pair of people was coloured by acquaintance, and enough people forced three who all knew each other or three who all did not. Here, every triple of points is coloured by the direction it turns — upward or downward, left to right — and enough points force $k$ whose triples all turn upward, or $l$ whose triples all turn downward.

Ramsey’s theorem for triples says that for any colouring of triples, enough points force a large set with all triples one colour. But the general bounds for triples grow like an exponential of an exponential, far worse than any binomial. What rescues this case is that the colouring by orientation is not arbitrary: if four points in order have their first three and last three turning upward, all four of their triples turn upward. That transitivity is what the meeting-point argument above exploits, and it is why orientation colourings have single-exponential answers while colourings in general need numbers nobody has ever seen.

What the searches can and cannot settle #

Every cup and cap in these figures is found by a search over all chains, and every construction is checked by the same search, so the small cases drawn are certified exactly. The eight-point set is certified by trying all fifty-six fives. What no search here reaches is the claim that nine points always contain a convex pentagon: that is a statement about every nine-point set, a continuum of them, and it was proved by a case analysis of their order types, not by sampling.

The same limitation applies to the bound’s exactness in general. The figures build the extremal sets up to forty points and check them. The recursion that builds them works for every $k$ and $l$; the check is what shows the recursion was implemented as described.

Still open: the happy ending conjecture itself #

Whether $N(k) = 2^{k-2} + 1$ for every $k$ is not known. It is proved for $k \le 6$. For $k = 7$ the conjecture predicts 33 points, and the search that settled $k = 6$ does not extend: the number of combinatorially different arrangements of 32 points is far beyond what can be enumerated, even using the symmetry the cup-and-cap structure provides.

Suk’s theorem says the conjecture is right up to a factor that grows more slowly than any exponential. Closing that last factor — or finding the first $k$ at which some set of $2^{k-2} + 1$ points avoids a convex $k$-gon — is the problem as it now stands. The construction that shows the lower bound is built from cups and caps, the upper bound is proved with them, and the truth, if the conjecture is right, is a statement about exactly how efficiently cups and caps can be packed along a dome.