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 |

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).