Let $S_n$ be the symmetric group equipped with uniform measure. For any $\pi\in S_n$, let $L_n=L_n(\pi)$ denote the longest increasing subsequence. A celebrated result of Baik, Deift and Johansson states that

$$P\left(\frac{L_n-2\sqrt{n}}{n^{1/6}}\leq s\right)\rightarrow F_2(s),$$

where $F_2(s)$ is the Tracy-Widom distribution, describing the largest eigenvalue of a GUE matrix. The connection between longest increasing subsequence, representation theory and random matrix theory is now well established.

Question: is there another natural statistic on $S_n$ resembling something akin to $L_n$ which follows a GOE distribution? Specifically, calling such a statistic $M_n$, I'm interested in a similar result of the form

$$P\left(\frac{M_n-2\sqrt{n}}{n^{1/6}}\leq s\right)\rightarrow F_1(s),$$ where $F_1(s)$ is now the Tracy Widom distribution of the largest eigenvalue of a GOE. Ideally, the scaling $n^{1/6}$ should be the same. I would also prefer to retain uniform measure on $S_n$ but, of course I would be very interested to hear of other examples. As well, the shift can be different as well.

I'm aware of numerous results in combinatorics where $F_1$ comes up in. For example, the fluctations of random aztec diamond tilings follow an Airy process and therefore have GOE behavior. There the scaling is $n^{1/3}$. As well, it comes up in viscous walkers and nonintersecting brownian motion. I mention these examples because there are definitely tangentially linked to $S_n$ through representation theory and growth processes. However, as I said I would ideally like an example of something that naturally occurs on $S_n$.


Involutions $s=s^{-1}$ in $S_n$ are modeled by the Tracy-Widom distribution $F_1$ for real symmetric matrices (GOE): Take as $S_n^\ast$ the subset of involutions in $S_n$, and let $M_n$ be the corresponding random variable for the longest increasing subsequence. Then the limit distribution is $$P\left(\frac{M_n − 2\sqrt n}{n^{1/6}}\leq s\right)\rightarrow F_1(s).$$

J. Baik and E.M. Rains, Symmetrized random permutations (1999).

The same paper also gives a generalization that is modeled by the Tracy-Widom distribution $F_4$ for the GSE (Gaussian symplectic ensemble). For a recent review article, see:

G. Olshanski, Random permutations and related topics (2011).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.