Skip to main content
Browse by:

Pattern-avoiding permutations and Dyson Brownian motion

Event Image
Thursday, October 04, 2018
3:15 pm - 4:15 pm
Erik Slivken (Paris Diderot)
Probability Seminar

Let \(S_n\) denote the set of permutations of length \(n\). For a permutation \(\tau \in S_n\) we say \(\tau\) contains a pattern \(\sigma\in S_k\) if there is a subsequence \(i_1 < \cdots < i_k\) such that \(\tau_{i_1} \cdots \tau_{i_k}\) has the the same relative order of \(\sigma\). If \(\tau\) contains no pattern \(\sigma\), we say that \(\tau\) avoids \(\sigma\). We denote the set of \(\sigma\)-avoiding permutations of length \(n\) by \(S_n(\sigma)\). Recently, there has been a number of results that help describe the geometric properties of a uniformly random element in \(S_n(\sigma)\). Many of these geometric properties are related to well-studied random objects that appear in other settings. For example, if \(\sigma \in S_3\), we have that a permutation chosen uniformly in \(S_n(\sigma)\) converges, in some appropriate sense, to Brownian excursion. Furthermore for \(\sigma = 123,312\) or\( 231\), we can describe properties like the number and location of fixed points in terms of Brownian excursion. Larger patterns are much more difficult to understand. Currently even the simplest question, enumeration, is unknown for the pattern \(\sigma = 4231\). However, for the monotone decreasing pattern \(\sigma= (d+1)d\cdots 21\), \(S_n(\sigma)\) can be coupled with a random walk in a cone that, in some appropriate sense, converges to a traceless Dyson Brownian motion.