The Universe of Discourse

Mark Dominus (陶敏修) [email protected]

About me

RSS Atom

12 recent entries

Archive:

---

Subtopics:

Comments disabled

Wed, 01 Sep 2021

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]S[i] is the position of letter ii in the string SS. Define the partial order ≺≺:

That is, i≺ji≺j means that ii is alphabetically earlier than jjand its position in SS is to the left of jj. This is obviously a partial ordering of the letters of the alphabet. Chains under ≺≺ are, by definition, ascending sequences of letters from SS. It's easy to show that antichains are descending sequences.

Partition SS into chains. If any chain has length 66 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 66 chains, because 5⋅5=255·5=25 and there are 2626 letters. Since there are at least 66 chains, Dilworth's theorem tells us there is an antichain of at least 66 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 ≺≺ 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 SS 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