On increasing subsequences of random permutations (Q1924244): Difference between revisions

Let \(L_n\) be the length of a longest increasing subsequence in a random permutation of \(1,2,\dots,n\). Further let \(E[L_n]\) and \(V[L_n]\) be the expected value and the variance of \(L_n\), respectively. It is well known that \((2-o(1))\sqrt n\leq E[L_n]\leq 2\sqrt n\). By some recent results of M. Talagrand, B. Bollobás and J. Janson, we have \(c_1n^{1/8}\leq V[L_n]\leq c_2n^{1/2}\). In this paper the author proves that \(L_n-2\sqrt n\) is at most order \(n^{1/6}\) with high probability, which suggests that \(V[L_n]\) might be \(n^{1/3}\). Moreover, the author conjectures that \(cn^{1/3}\leq V[L_n]\leq c'n^{1/3}\) for some positive constants \(c\) and \(c'\).