UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Patience Sorting and Barred Permutation Patterns

Algebra & Discrete Mathematics

Speaker: Isaiah Lankham, UC Davis
Location: 1147 MSB
Start time: Thu, Mar 30 2006, 12:10PM

Despite having been introduced in 1962 by C.L. Mallows, the combinatorial algorithm \emph{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. At the same time, Patience Sorting can also be viewed as an iterated, non-recursive form of the famed Schensted Insertion Algorithm.

In this talk we will begin by surveying some of these connections. We will then detail several recent results that characterize various combinatorial properties of Patience Sorting in terms of permutation pattern avoidance. In particular, we will show that Patience Sorting provides an algorithmic description for permutations avoiding the barred (generalized) permutation pattern $3-\bar{1}-42$. We will also characterize those permutations for which Patience Sorting is an invertible algorithm as the set of permutations simultaneously avoiding the barred patterns $3-\bar{1}-42$ and $3-\bar{1}-24$. This is joint work with Alex Burstein (Iowa State University).