Stack Sorting and Permutation Patterns

Murray Elder
Department of Mathematical Sciences
Stevens Institute of Technology

Tuesday, October 10, 3:00PM
Lieb, Room 319
Stevens Institute of Technology
 

Abstract

I will discuss my recent work in the field of "pattern avoiding permutations". A permutation p_1, p_2,..., p_n of 1,2,...,n is said to contain a subpattern (213 say) if some p_{i_1}, p_{i_2}, p_{i_3} occur with p_{i_2} < p_{i_1} < p_{i_3}.

Knuth proved that if you pass a mixed-up permutation through a single infinite stack, then it can be sorted back to 1,2,...,n if and only if it does not contain a 213 subpattern. It follows that the number of such permutations is Catalan.

I will give an overview of the recent results about pattern-avoiding permutations, and give my result about sorting permutations with two stacks in series.