Combinatorics Seminar- Patterns in Random Permutations

Speaker: Chaim Even Zohar, UC Davis
Date and time: Monday, February 25, 4-5pm
Place: Rome 206
Title: Patterns in Random Permutations

Abstract: Every k entries in a permutation can have one of k! different relative orders, called patterns. How many times does each pattern occur in a large random permutation of size n? The distribution of this k!-dimensional vector of pattern densities was studied by Janson, Nakamura, and Zeilberger (2015). Their analysis showed that some component of this vector is asymptotically multinormal of order 1/sqrt(n), while the orthogonal component is smaller. Using representations of the symmetric group, and the theory of U-statistics, we refine the analysis of this distribution. We show that it decomposes into k asymptotically uncorrelated components of different orders in n, that correspond to representations of S_k. Some combinations of pattern densities that arise in this decomposition have interpretations as practical nonparametric statistical tests.