The question When should we expect TracyWidom? motivated me to post the following question, in which I have been interested for a while. Let $f(n)$ be a function from the positive integers to themselves. Given a permutation $w=a_1\cdots a_n\in S_n$, let $m=f(n)$ and let $L_f(w)$ be the length $k$ of the longest subsequence $b_1 \cdots b_k$ of $w$ satisfying $$ b_1<b_2<\cdots <b_{m+1}>b_{m+2}>b_{m+3}>\cdots>b_{2m+1}<b_{2m+2}< \cdots <b_{3m+1}>\cdots. $$ If we scale $L_f$ suitably then it should approach a limiting distribution $\Phi(t)$ as $n\to\infty$. For $f(n)=1$ it is known that $\Phi(t)$ is Gaussian. For $f(n)=n$ it is known that $\Phi(t)$ is the TracyWidom distribution. See for instance http://math.mit.edu/~rstan/papers/ids.pdf (Theorems 4 and 14). What happens in between these two extremes, e.g., $f(n)=\log n$ or $\sqrt{n}$? Do we always get either a Gaussian or TracyWidom distribution? If so, what is the crossover point? If not, what other distributions are possible?

$\begingroup$ In the interest of clarity, can you tell us what w is and what w and the a's have to do with L_f(w) ? Also, I am guessing that f(n) > n is an f that plays no role in this problem. Or can it? $\endgroup$ – The Masked Avenger Jun 25 '15 at 5:59

$\begingroup$ @TheMaskedAvenger: I have added the fact that $w=a_1\cdots a_n$. The case $f(n)>n$ is equivalent to $f(n)=n$. $\endgroup$ – Richard Stanley Jun 25 '15 at 7:41

$\begingroup$ A trivial observation: there's some strange parity here. The Tracy widom distribution is biased toward one side, whereas the Gaussian is symmetric about the mean. This is evident here since for small $m$, we basically have reflection symmetry. So I would expect the transition to occur when $m\gg n/2$. $\endgroup$ – Alex R. Jun 25 '15 at 17:50

$\begingroup$ In particle systems or random matrices the phase transition from Gaussian to TracyWidom is known, it is given by BaikBen ArousPeche distribution (or maybe in this case GOE TracyWidom which is a particular case) $\endgroup$ – Leonid Petrov Nov 25 '16 at 3:04