Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The study of Permutation Patterns (and in particular permutations avoiding certain patterns), has recently become a very hot research topic because of it's many applications to fields ranging from Algebraic Combinatorics to Statistical Learning Theory. In the early 1990's Richard Stanley and Herbert Wilf made a very insightful and fundamental conjecture that gives an upper bound on the number of permutations avoiding a given patterns. Until recently, various authors have tried repeated to prove this theorem but had only been able to prove it for certain special cases. However, in November 2003 A. Marcus and G. Tardos were able to prove the full conjecture as a corollary to other well-known conjecture.

In this talk we will first discuss what a permutation pattern is and why one might want to avoid them. Then we will survey what is known about avoiding certain patterns. We will then discuss the Stanley-Wilf ex-Conjecture, its refinements, other important related conjecture, and how A. Marcus and G. Tardos were able to prove it.

Required prerequisite knowledge of combinatorics will be kept to a minimum.