# Extrapolation between longest increasing and longest alternating subsequences

The question When should we expect Tracy-Widom? 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 Tracy-Widom 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 Tracy-Widom distribution? If so, what is the crossover point? If not, what other distributions are possible?

• 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? – The Masked Avenger Jun 25 '15 at 5:59
• @TheMaskedAvenger: I have added the fact that $w=a_1\cdots a_n$. The case $f(n)>n$ is equivalent to $f(n)=n$. – Richard Stanley Jun 25 '15 at 7:41
• 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$. – Alex R. Jun 25 '15 at 17:50
• In particle systems or random matrices the phase transition from Gaussian to Tracy-Widom is known, it is given by Baik-Ben Arous-Peche distribution (or maybe in this case GOE Tracy-Widom which is a particular case) – Leonid Petrov Nov 25 '16 at 3:04