The sequence that cannot avoid a staircase

The Ramsey results so far in this ladder force a structure inside a colouring. This one forces a structure inside an ordering, and it is the sharpest of the family: the bound is exact, the proof is four lines, and the extremal case can be written down.

Any sequence of more than $n^2$ distinct numbers contains an increasing subsequence of length $n+1$ or a decreasing one.

The two counters #

Give each term of the sequence two numbers: the length of the longest increasing subsequence ending at it, and the length of the longest decreasing subsequence ending at it. Call them $u_i$ and $d_i$.

No two terms can carry the same pair. Take $i < j$. If $a_i < a_j$, then any increasing run ending at $a_i$ extends to $a_j$, so $u_j > u_i$. If $a_i > a_j$, then the same argument on the decreasing side gives $d_j > d_i$. Either way the pairs differ.

Now suppose no climb and no fall is longer than $n$. Then every $u_i$ and every $d_i$ lies between 1 and $n$, so there are $n^2$ possible pairs, and since the pairs are all different, there are at most $n^2$ terms.

That is the whole proof. It is a pigeonhole — more things than boxes — with the boxes being the pairs and the observation that no two things share one.

The figure computes both counters for every term of the sequence it draws and asserts that all the labels are distinct, which is the load-bearing claim. It then adds one more term and asserts that a climb or a fall of length $n+1$ appears.

The extremal sequence #

The bound is exactly achieved, which is unusual in this subject and worth seeing.

Take $n$ blocks of $n$ numbers each. Within a block the numbers descend; across blocks they ascend, so that every number in a later block is larger than every number in an earlier one. For $n = 3$: $3, 2, 1, 6, 5, 4, 9, 8, 7$.

An increasing subsequence can take at most one term from each block, so has length at most $n$. A decreasing subsequence must stay inside a block, since crossing to a later block means increasing, so also has length at most $n$. And there are $n^2$ terms.

So $n^2$ is the right number and $n^2 + 1$ is forced. The bound and the construction meet exactly, which is what distinguishes this from $R(k,k)$, where the two are exponentially far apart.

What the counters are counting #

It helps to read the pair of counters as a coordinate rather than as bookkeeping.

Plot each term at the point $(u_i, d_i)$. The claim that no two terms share a pair is the claim that the terms land at distinct lattice points, and the claim that both counters are at most $n$ is the claim that all those points lie inside an $n$ by $n$ square. A square of side $n$ has $n^2$ lattice points; a sequence of $n^2+1$ terms would need $n^2+1$ of them.

Seen that way the extremal construction is not an ingenious arrangement but the only thing that can work: it must fill the square exactly, one term per cell. And it does — the $j$-th term of the $i$-th block has climb $i$ and fall $j$, so the blocks are the rows and the positions within them are the columns.

The proof and the construction are therefore the same object approached from two sides, which is the sign of a bound that is going to be exact.

Why it is a Ramsey theorem #

The result predates Ramsey’s paper by a couple of years and is usually classed with it, and the classification is right for a reason worth stating.

A sequence of distinct numbers determines a colouring of pairs: colour $\{i, j\}$ with $i < j$ by whether $a_i < a_j$. An increasing subsequence is a set of positions all of whose pairs get the first colour; a decreasing one, the second. So the statement is exactly Ramsey’s theorem for this particular family of colourings — and the reason the bound is so much better is that not every colouring of pairs arises this way.

A general two-colouring can be anything. A colouring coming from an ordering must be transitive: if $a_i < a_j$ and $a_j < a_k$ then $a_i < a_k$. That extra structure is what takes the bound from exponential to quadratic, and it is a good illustration of how much Ramsey-type bounds depend on how arbitrary the colouring is allowed to be. The probabilistic lower bound works precisely because a random colouring is arbitrary, and it has nothing to say here, because a random colouring is almost never transitive.

Dilworth, and the same argument again #

There is a second reading which generalises further.

Order the terms by position and value at once: say $i \preceq j$ when $i \leq j$ and $a_i \leq a_j$. That is a partial order on the terms. A chain in it is an increasing subsequence; an antichain — a set of pairwise incomparable terms, — is a decreasing subsequence, since terms later in position and smaller in value are incomparable.

Dilworth’s theorem — the one Sperner’s sits beside — says a partial order with no antichain larger than $w$ splits into $w$ chains. Applied here: no decreasing subsequence longer than $n$ means the terms split into $n$ increasing subsequences, so if there are more than $n^2$ terms one of those chains has more than $n$, giving a long climb.

That is the same theorem obtained from a general one, and it is worth having both. The counter argument is shorter and specific; the Dilworth argument explains why the bound is a product, and generalises to settings with no sequence in them.

The happy ending problem #

Erdős and Szekeres proved their theorem while working on a different question, posed by Esther Klein, which is the other half of this rung.

Any five points in general position contain four in convex position.

The proof is a case split on the hull, and the three cases are the three panels.

Hull of five. Any four of them are in convex position; nothing to do.

Hull of four. The hull is a convex quadrilateral already.

Hull of three. Two points lie inside a triangle. Draw the line through them; it cuts the triangle so that two of the three corners are on the same side. Those two corners together with the two interior points form a convex quadrilateral — and the reason is that the line separates one corner from the other two, so the four chosen points have none inside the hull of the others.

The general question — how many points force a convex $k$-gon — is called the happy ending problem, because Klein and Szekeres married. Erdős and Szekeres proved that a finite number always suffices, conjectured that it is $2^{k-2} + 1$, and proved that in 1935 for $k = 4$ and 5. The case $k = 6$ was settled by computer in 2006, at 17 points as conjectured. The general conjecture is still open, though the upper bound was brought down to $2^{k + o(k)}$ in 2016 — matching the conjecture’s base at last.

Why the two are the same subject #

The connection between the sequence theorem and the points problem is direct.

Given points in general position with no two sharing an $x$-coordinate, sort them by $x$ and read off the sequence of $y$-coordinates. An increasing run is a set of points going up and to the right; a decreasing run goes down and to the right. Erdős–Szekeres then gives a long monotone run among any large set of points.

A monotone run is not convex by itself, but it is a set of points forming a cap or a cup once a second application is made — and the original 1935 proof is exactly a two-parameter version of the counter argument, tracking the largest cap and the largest cup ending at each point instead of the largest climb and fall. The $2^{k-2}$ in the conjecture is the binomial coefficient that comes out of that recursion.

So the sequence theorem is a warm-up for the geometry, and it is the warm-up that turned out to be exactly solvable while the geometry did not.

What is being forced, and by how little #

One last observation about how tight this is, since tightness is the rung’s distinguishing feature.

$R(3,3) = 6$ means that five points can escape and six cannot, and the escape at five is a delicate arrangement. Here, $n^2$ terms can escape and $n^2+1$ cannot, and the escape at $n^2$ is delicate in the same way: the counters must fill the square exactly, so every extremal sequence is the block construction up to relabelling, and there is no room at all.

Compare what happens either side. At $n^2 - 1$ terms there is slack and many arrangements avoid long runs; at $n^2 + 1$ there is none. A threshold with exactly one extremal configuration is the sharpest kind there is, and it is rare — the pentagon that saves five people is another, and the two are among the very few in this subject. Both are cases where the pigeonhole has been applied to boxes that are exactly filled rather than merely overfull.

The rigidity has a practical consequence. Because the extremal case is unique and describable, the theorem can be used in the contrapositive: a sequence that is not the block construction has a monotone run longer than $n$ before it reaches $n^2$ terms. That is a much stronger statement than the theorem as usually quoted, and it comes free from the proof.

What the picture cannot show #

The extremal sequences drawn here are the standard block construction, and the theorem’s claim is about every sequence of $n^2 + 1$ terms. What the figures verify is that one particular arrangement achieves the bound and that adding one term to it breaks; the general statement is the four-line argument, and no picture of any sequence proves it.

The convex-position figure has the same limitation in a sharper form. Three point sets are drawn and the claim is about all of them, so the figure runs the check over four thousand seeded sets in general position — which is evidence rather than proof, and is described as such in the caption. The proof is the hull case split, which needs no examples at all.

And nothing here can show the happy ending problem’s difficulty. Five points and four in convex position is a case split; seventeen points and six in convex position took a computer search over a space that had to be cut down by a great deal of theory first, and there is no picture of that.

Where the theorem is used #

It is worth naming two uses, because a theorem this tight tends to be a tool rather than a destination.

Sorting and patience. Dealing a shuffled pack into piles, each card going on the leftmost pile whose top card is larger, produces a number of piles equal to the length of the longest increasing subsequence. That is not a coincidence but Dilworth’s theorem in action, and the algorithm — patience sorting — computes the quantity in $n\log n$ time. The proof above says that this number times the longest decreasing run is at least the length of the sequence.

Bounding what a comparison can learn. Any algorithm that only compares elements is working with the partial order above — and what a sorting network can decide is bounded by the structure it can force, and the theorem bounds how much structure a sequence can hide from it. That kind of statement is what lower bounds on sorting and searching are built from.

The general pattern is that a theorem forcing structure is useful as a guarantee: something is always there, so an algorithm may rely on finding it. The Ramsey theorems in the rest of this ladder rarely offer that, because the sizes at which their structures appear are far beyond any computation.

The random case, which is a different shape entirely #

The theorem is about the worst case, and the typical case is worth a paragraph because the two answers look nothing alike.

A random permutation of $n$ numbers has a longest increasing subsequence of length about $2\sqrt n$. Not $\sqrt n$, which is what the theorem’s bound would suggest if the two runs were balanced — twice that, and the factor of two took decades to establish.

So the extremal sequence, with both runs at exactly $\sqrt n$, is far from typical: a random permutation has runs twice as long in both directions. The worst case is worse than random by a factor of two, which is a small margin by the standards of this subject and is a consequence of how tight the bound is.

The distribution of that length is the celebrated part. Its fluctuations about $2\sqrt n$ are of order $n^{1/6}$ and follow the Tracy–Widom law, which arose first in the study of eigenvalues of random matrices and has no obvious business appearing in a question about shuffling cards. That connection, established in 1999, is one of the more surprising in modern probability, and it starts from the theorem in this essay.

The ladder from here #

Rungs above: the cap-and-cup proof, and where the binomial coefficient comes from. Dilworth’s theorem and Mirsky’s, proved rather than quoted. The Robinson–Schensted correspondence, which turns a permutation into a pair of tableaux whose shape encodes the longest climb and fall together — a much finer statement than the theorem here. The distribution of the longest increasing subsequence of a random permutation, which is $2\sqrt n$ and whose fluctuations are one of the celebrated results of the last thirty years. And the happy ending problem’s upper bound.

Why this one is exact #

Every other rung of this ladder has a gap between what is forced and what can be exhibited, and this one does not. It is worth asking what is different.

The answer is that the counting is injective. The proof does not say that some pair of counters must repeat because there are too many terms; it says that no pair can repeat, ever, and then counts the pairs. That is a much stronger statement than pigeonhole usually delivers, and it is what makes the bound exactly right rather than merely a bound.

The general lesson is worth carrying. A pigeonhole argument gives a sharp answer exactly when the map into the boxes is injective and the boxes are all reachable — one term per pair, and the block construction reaching every pair. When either half fails, the bound is loose, and the Ramsey numbers are what loose looks like.