UC Davis Mathematics

Mathematics Colloquia and Seminars

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