Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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