Fall 2014: Theory Seminar
Donald Bren Hall, Room 1425, 1:00pm
October 31, 2014:

Fast Sorting and Pattern-Avoiding Permutations

Will Devanny

We say a permutation $\pi$ “avoids” a pattern $\sigma$ if no length $|\sigma|$ subsequence of $\pi$ is ordered in precisely the same way as $\sigma$. For example, $\pi$ avoids $(1, 2, 3)$ if it contains no increasing subsequence of length three. It was recently shown by Marcus and Tardos that the number of permutations of length $n$ avoiding any fixed pattern is at most exponential in $n$. This suggests the possibility that if $\pi$ is known a priori to avoid a fixed pattern, it may be possible to sort $\pi$ in as little as linear time. Fully resolving this possibility seems very challenging, but in this paper, we demonstrate a large class of patterns $\sigma$ for which $\sigma$-avoiding permutations can be sorted in $O(n\log\log\log n)$ time.

(Based on a paper by David Arthur from ANALCO 2007.)