Let $S_n$ be the symmetric group, $\pi\in S_n$ a uniformly random permutation and $L_n:=L_n(\pi)$ denoting the length of the longest increasing subsequence (LIS). We know that $\lim_{n\rightarrow\infty}\frac{E[L_n]}{2\sqrt{n}}=1$. My question is, what is known about the finer aspects of the growth rate of $E[L_n]$? Specifically

Is there an explicit formula for $E[L_n]$ (not involving sums over tableaux dimesions) which captures the finer asymptotics of $E[L_n]$?

Edit: to clarify, as per Richard Stanley's comment:

$$E[L_n]=2\sqrt{n}+\alpha n^{1/6}+o(n^{1/6}),$$

where $\alpha$ is the mean of the Tracy-Widom $F_2$ distribution. My question is, what is known about the $o(n^{1/6})$ terms?

I would think that one can massage Gessel's Bessel generating function expression for $P(L_n\leq t)$ (there's also a Toeplitz determinant expression) to obtain something for $E[L_n]$. But is the result tractable for analyzing $E[L_{n+1}]-E[L_n]$? According to an old paper by Odlyzko, the difference is conjectured to be on the order of $o(n^{1/6})$, which is correct but I could not find any finer expression.

There's a trove of literature on the random matrix connections to the distribution of $L_n$ but, I've had trouble finding specific work done on analyzing the finer aspects of $E[L_n]$.

I would sincerely appreciate links to relevant references!

  • 2
    $\begingroup$ One reference is math.mit.edu/~rstan/papers/ids.pdf. See equation (15) in particular. $\endgroup$ – Richard Stanley Feb 18 '15 at 22:51
  • $\begingroup$ @RichardStanley: Ah, thanks! Do you happen to know if the higher (third order) terms are known? I guess I should edit my question to emphasize this. $\endgroup$ – Alex R. Feb 18 '15 at 22:56
  • 1
    $\begingroup$ A higher order term is not known. It is not known whether there even is a next term. $\endgroup$ – Richard Stanley Feb 19 '15 at 0:17
  • 1
    $\begingroup$ @RichardStanley comment -> answer? $\endgroup$ – usul Feb 19 '15 at 0:26

Your Answer

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

Browse other questions tagged or ask your own question.