Aldous/Diaconis: Longest Increasing Subsequences

For some research I'm currently doing, I ran across a truly wonderful "old" paper,
Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
by Aldous and Diaconis, which appeared in the Bulletin of the American Mathematical Society back in 1999.  It's easily findable online.

The fun in this paper is that it highlights the probabilists' notion of reduction, which is similar but slightly different from the standard CS notion.  Generally, it involves taking one process or class of objects and mapping it (usually bijectively) to another process or class of objects that can be analyzed.  And longest increasing subsequences, as it turns out, can be mapped into lots of things.  For example, a standard connection is with greedy patience sorting.  Here's the example from the paper.  Take a shuffled deck of cards:

7 2 8 1 3 4 10 6 9 5

Greedy patience sorting puts the cards into piles using the following rules:
1)  A card can be placed on top of any higher card.  When being greedy, we place the card on the leftmost possible pile.
2)  If no higher card is showing, thc card starts a new pile to the right of all other piles.

So for this sequence, the piles appears as follows (with the top card bolded for each pile.

7
------
2
7
------
2
7  8
------
1
2
7  8
------
1
2  3
7  8
------
1
2  3
7  8  4
------
1
2  3
7  8  4  10
------
1
2  3       6
7  8  4  10
------
1
2  3       6
7  8  4  10  9
------
1           5
2  3       6
7  8  4  10  9
------

The longest increasing subsequence is equal to the number of piles at the end of patience sorting.  (Exercise, left to reader.) 

The paper then goes on to show other objects that connect to the longest increasing subsequence, including Young tableaux, an interacting particle system on the real line, and determinants of certain matrices.  These connections allow various analyses of longest increasing subsequences on random permutations.

The longest increasing subsequence, by itself, certainly sounds like a nice problem, but when you see these mappings to a variety of different objects, you're overwhelmed by the feeling that there's something fundamental there -- worth learning more about.  And that's what makes the paper such a fun read.