Return to Colloquia & Seminar listing
Patience Sorting and Barred Permutation Patterns
Student-Run Discrete Mathematics| Speaker: | Isaiah Lankham, UC Davis |
| Location: | 1147 MSB |
| Start time: | Thu, Jan 11 2007, 11:00AM |
Description
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).