How long a monotonic subsequence must a random permutation of an alphabet contain?

The question’s pretty much as it is in the tile. If you permute an ordered alphabet with n letters, then there has to be a subsequence which is either strictly increasing or strictly decreasing. How short can that subsequence be? I wish I was knowledgeable enough for this to be homework.


It should always be possible to create a permutation that’s alternately increasing and decreasing, no? Start with the first letter of the alphabet, then the last letter, then the second letter, then the penultimate letter, and so on. This answer is simple and trivial enough that I suspect that there’s some other criterion you intended to add…

Just to clarify, I’m asking about subsequences, not substrings. The latter have to be contiguous, but the former do not. So if you have the string “azbycxdw”, it doesn’t have a monotonic substring longer than one, but “abcd” and “zyxw” are both monotonic subsequences of length four.

Erdős-Szekeres Theorem.

In general, n - 1 can be written as the product of two naturals in multiple ways. How do you decide which values to use? In particular, since ab = ba, how do you decide which factor to use for the length of the increasing subsequence?

However you like; the theorem is basically saying that if you only allow short increasing subsequences, you will get long decreasing subsequences. If you’re only interested in minimizing the maximum-length monotone subsequence (and don’t care whether it’s increasing or decreasing) then you’d choose a=b, meaning that the maximum monotone subsequence is always at least about sqrt(n) long.

Unless I misunderstand what you mean, it has lots of monotonic substrings of length two. Assuming the elements are completely ordered, every substring of length two must be either increasing or decreasing (weakly if you allow repeats and strictly if you don’t as here.)

Ah, apologies on misunderstanding the question, then. I should have remembered the definition of “subsequence”, but I’d only seen it in one math class, several years ago.

Could someone explain this theorem to me. I am completely lost. What does the theorem say about the longest subsequence of the regular alphabet of 26 letters?

There has to be one of length 6. (The square root of 26 is 5+ so it rounds up to 6. If was a 25 character alphabet, then it would be 5.)

The Wikipedia article explains the bound a little more (plus a link to a survey paper). Note that the way way ultrafilter phrases it, one needs only a single parameter: n the sequence length. But the ES theorem is dual parameter: given bounds for max. increasing and decreasing subsequences (r and s), how long is must the sequence be. By setting r=s, then one gets the sqrt(n) bound.

OTOH, matching the bound is easy to see, here’s how to maximize it for the letters a-y (25).

uvwxy pqrst klmno fghij abcde

I broke them into 5 groups of 5. Each group increases but the groups overall decrease. If you want a decreasing subsequence, you can only pick one per group, so 5 max. If you want an increasing subsequence, you can’t pick from two different groups, again 5 max.

It’s not all that common for something related to Ramsey’s theorem to have a simple tight bound.

Does the theorem say that this is necessarily the minimum length? That is, if you did an exhaustive search, could there be some n where the true minimum is larger than what the theorem tells you?

The bound is tight; ftg’s example shows an example of such a minimal sequence. More generally, if you have an ab-character alphabet, you can break it into a list of b strings of a characters, and reverse the list. So for a=3, b=4, reorder the 12-character alphabet ABCDEFGHIJKL as JKL GHI DEF ABC, which obviously has maximum ascending subsequence length 3 and maximum descending subsequence length 4. So for any n<ab+1, an n-character alphabet need not have either an increasing (a+1)-character subsequence or a decreasing (b+1)-character sequence; and the theorem’s bound is tight.