Longest alternating subsequences of permutations. Richard P. Stanley (MIT). In the past decade or so, there’s been a surprisingly big fuss over what might seem to be a very small question: What is the distribution of the longest increasing subsequence in a random permutation of integers? Here’s an example of such a permutation—a random ordering of the integers from 0 through 9:
{2 4 9 6 3 5 0 7 1 8}
A subsequence of the permutation is a set of numbers drawn from this list in order, from left to right, but the numbers needn’t be consecutive elements of the list. For example, {2 6 8} is a subsequence of the permutation—indeed, it is an increasing subsequence. The process of searching for the longest increasing subsequence has a certain tension built in to it: You want to start as far to the left as possible but you also want to start with a small number, and those two desiderata may be in conflict. In this case the longest increasing subsequences have five elements, and there are three of them: {2 3 5 7 8}, {2 4 5 7 8} and {2 4 6 7 8}.
Finding the longest subsequences in any specific permutation is not much of a challenge (but see the note below). What interests mathematicians is the distribution of lengths of longest subsequences for large samples of permutations. After much labor, the exact nature of that distribution was pinned down a few years ago by Jinho Baik, Percy Deift and Kurt Johansson. The answer turns out to be a very complicated mathematical object. It was worth expending all that effort to find the answer because the longest-increasing-subsequence problem has connections to many distant areas of mathematics and physics, even including the airplane boarding problem discussed here a few days ago. (If you want to know more, see the review article by David Aldous and Persi Diaconis.
Richard P. Stanley has looked at a variation on this problem: instead of counting increasing subsequences, he looks at alternating subsequences, those with a “sawtooth” profile of alternating ascents and descents. In the permutation given above, the longest alternating subsequences have eight elements. There are five of them: {2 4 3 5 0 7 1 8}, {2 6 3 5 0 7 1 8}, {2 9 3 5 0 7 1 8}, {4 6 3 5 0 7 1 8} and {4 9 3 5 0 7 1 8}. Why do alternating sequences grow longer than increasing ones? Basically, because there are more ways to form an alternating subsequence. It turns out that the distribution of longest alternating subsequences is much easier to describe and understand than that of longest increasing subsequences. On the other hand, so far these sequences have none of the ramifications or applications of the increasing ones. For more, see the online Postscript version of Stanley’s talk.
Note: I remarked above that it’s not much of a challenge to find the longest subsequences in a specific permutation, but I have to confess that the task gave me a spot of trouble. I didn’t trust myself to identify the longest increasing and alternating subsequences by hand, so I wrote a little program to do it. I thought that would take a few minutes. But generating subsequences is one of those problems that looks easy only until you decide you’d like to get the right answer.
Update (July 7, 2006): A little late, I’ve just learned that Harold Widom of the University of California at Santa Cruz has proved that the distribution has the form conjectured by Stanley. Widom’s paper is here.