Return to Colloquia & Seminar listing
Combinatorics of the Patience Sorting Algorithm
Algebra & Discrete Mathematics| Speaker: | Isaiah Lankham, U C Davis |
| Location: | 693 Kerr |
| Start time: | Mon, Apr 11 2005, 3:10PM |
Description
Despite having been introduced in 1962 by C.L. Mallows, the
combinatorial algorithm "Patience Sorting" has only recently received
significant attention due to the celebrated Baik-Deift-Johansson Theorem,
which links Patience Sorting to fields including Probabilistic
Combinatorics and Random Matrix Theory.
In this talk we will begin by surveying some of these connections. We will
then detail the combinatorics of the Patience Sorting Algorithm by
exploiting similarities between it and the famous Schensted Insertion
Algorithm for Young Tableaux. This will allow us to define an analog of
the Knuth relations and extend Patience Sorting to a bijection between
permutations and certain pairs of set partitions. As an application of
these constructions we characterize and enumerate permutations avoiding
the generalized pattern 3-\bar{1}-42.
This is joint work with Alex Burstein (Iowa State University).