Algebraic Combinatorics Seminar
####
**
UNIVERSITY OF KENTUCKY **

ALGEBRAIC COMBINATORICS SEMINAR

845 PATTERSON OFFICE TOWER

SPRING 2004

####

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