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 $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$ 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?
Extrapolation between longest increasing and longest alternating subsequences
Richard Stanley
- 50.8k
- 14
- 155
- 279