Quicklists
public 46:08

Pratima Hebbar, Probability Seminar

  -   Uploaded by nolen ( 211 Views )

Pratima Hebbar, Probability Seminar on October 21, 2021

public 01:24:57

Erik Slivken : Pattern-avoiding permutations and Dyson Brownian motion

  -   Uploaded by root ( 78 Views )

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.