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