When the law of large numbers fails for increasing subsequences of random permutations

Let the random variable $Z_{n,k}$ denote the number of increasing subsequences of length $k$ in a random permutation from $S_n$, the symmetric group of permutations of $\{1,\mathrm{.}\mathrm{.}\mathrm{.},n\}$. In a recent paper [Random Structures Algorithms 29 (2006) 277–295] we showed that the weak law of large numbers holds for $Z_{n,k_n}$ if $k_n=o(n^{2\mathrm{/}5})$; that is, $$\underset{n\to \mathrm{\infty }}{\lim }\frac{Z_{n,k_n}}{E{Z}_{n,k_n}}=1inprobability\mathrm{.}$$ The method of proof employed there used the second moment method and demonstrated that this method cannot work if the condition $k_n=o(n^{2\mathrm{/}5})$ does not hold. It follows from results concerning the longest increasing subsequence of a random permutation that the law of large numbers cannot hold for $Z_{n,k_n}$ if $k_n\ge c{n}^{1\mathrm{/}2}$, with $c>2$. Presumably there is a critical exponent $l_0$ such that the law of large numbers holds if $k_n=O(n^l)$, with $l<l_0$, and does not hold if ${\mathrm{lim\hspace{0.17em}sup}}_{n\to \mathrm{\infty }}\frac{k_n}{n^l}>0$, for some $l>l_0$. Several phase transitions concerning increasing subsequences occur at $l=1\mathrm{/}2$, and these would suggest that $l_0=1\mathrm{/}2$. However, in this paper, we show that the law of large numbers fails for $Z_{n,k_n}$ if ${\mathrm{lim\hspace{0.17em}sup}}_{n\to \mathrm{\infty }}\frac{k_n}{n^{4\mathrm{/}9}}=\mathrm{\infty }$. Thus, the critical exponent, if it exists, must satisfy $l_0\in [2\mathrm{/}5,4\mathrm{/}9]$.