Pattern Avoidance

Neil Moore

Friday, April 2, 2004
11:00 am, 845 Patterson Office Tower

Abstract:

Let t be a fixed permutation in the symmetric group S_k (the "pattern") and let s be a permutation in S_n. We say that s contains t if the sequence s(1)s(2)...s(n) contains a subsequence that is order-isomorphic with t(1)t(2)...t(k); otherwise, we say that s avoids t. We present results of Noga Alon and Ehud Friedgut, Richard Arratia, and others, which establish asymptotic bounds on the number of n-permutations containing t.