Stable characters from permutation patterns

Abstract

For a fixed permutation $\sigma \in S_k$, let $N_{\sigma }$ denote the function which counts occurrences of $\sigma$ as a pattern in permutations from $S_n$. We study the expected value (and dth moments) of $N_{\sigma }$ on conjugacy classes of $S_n$ and prove that the irreducible character support of these class functions stabilizes as n grows. This says that there is a single polynomial in the variables $n, m_1, \ldots , m_{dk}$ which computes these moments on any conjugacy class (of cycle type $1^{m_1}2^{m_2}\cdots$) of any symmetric group. This result generalizes results of Hultman (Adv Appl Math 54:1–10, 2014) and of Gill (The k-assignment polytope, phylogenetic trees, and permutation patterns, Ph.D. Thesis at Linköping University, pp 103–125, 2013), who proved the cases $(d,k)=(1,2)$ and (1, 3) using ad hoc methods. Our proof is, to our knowledge, the first application of partition algebras to the study of permutation patterns.