The Most and the Least Avoided Consecutive Patterns

Monday, November 10, 2014 - 11:00am - 11:25am
Keller 3-180
Sergi Elizalde (Dartmouth College)
A permutation pi avoids a consecutive pattern sigma if no subsequence of adjacent entries of pi is in the same relative order as the entries of sigma.

We show that the number of permutations avoiding the consecutive pattern dots m --that is, containing no m adjacent entries in increasing order-- is asymptotically larger than the number of permutations avoiding any other consecutive pattern of length m. This had been conjectured in 2001 by Elizalde and Noy. At the other end of the spectrum, the number of permutations avoiding 12...(m-2)m(m-1) is asymptotically smaller than for any other consecutive pattern. This had been conjectured by Nakamura.
MSC Code: