The Universe of Disco

On having the right theorem

A recent Math StackExchange question asks “Prove every permutation of the alphabet contains a subset of six letters in order”. That is, you take a string of length 26 that contains each letter once; you can find a subsequence of six letters that is either increasing or decreasing.

Choosing a permutation at random, suppose we have:

    q y x u l i n g w o c k j d r p f v t s h e a z b m

Then the sequence x w v t s e b has length 7 and is in descending order. Or:

    t h e q u i c k b r o w n f x j m p s v r l z y d g

This contains the ascending sequence h q r s v y. Also the descending sequence t q o n m l d.

I thought about this for a while but couldn't make any progress. But OP had said “I know I have to construct a partially ordered set and possibly use Dilworth's Theorem…” so I looked up Dilworth's theorem.

It turns out I did actually know Dilworth's theorem. It is about partially-ordered sets. Dilworth's theorem says that if you partition a partially-ordered set into totally-ordered subsets, called ‘chains’, then the number of such chains is at least as big as the size of the largest “antichain”. An antichain is a subset in which no two elements are comparable.

This was enough of a hint, and I found the solution pretty quickly after that. Say that !!S[i]!! is the position of letter !!i!! in the string !!S!!. Define the partial order !!\prec!!: $$ i\prec j \qquad \equiv \qquad i < j \text{ and } S[i] < S[j] $$

That is, !!i\prec j!! means that !!i!! is alphabetically earlier than !!j!! and its position in !!S!! is to the left of !!j!!. This is obviously a partial ordering of the letters of the alphabet. Chains under !!\prec!! are, by definition, ascending sequences of letters from !!S!!. It's easy to show that antichains are descending sequences.

Partition !!S!! into chains. If any chain has length !!6!! or more, that is an ascending sequence of letters and we win.

If not, then no chain has more than 5 letters, and so there must be at least !!6!! chains, because !!5·5=25!! and there are !!26!! letters. Since there are at least !!6!! chains, Dilworth's theorem tells us there is an antichain of at least !!6!! letters, and hence a descending sequence of that length, and we win.

Once you have the idea to use Dilworth's theorem, the problem collapses. (You also have to invent the right !!\prec!! relation, but there's really only one possible choice.)

Maybe I'll write a followup article about how just having a theorem doesn't necessarily mean you have an algorithm. Mathematicians will say “partition !!S!! into chains,” but actually programming something like that might be nontrivial. Then finding the antichain among the chains might also be nontrivial.

[Other articles in category /math] permanent link