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,...,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/5})$; that is, \[\lim_{ n\to\infty}\frac{ Z_{ n,k_n}}{ EZ_{ n,k_n}}=1\qquad in probability.\] 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/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 cn^{ 1/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 $\limsup_{ n\to\infty}\frac{ k_n}{ n^l}>0$, for some $l>l_0$. Several phase transitions concerning increasing subsequences occur at $l=1/2$, and these would suggest that $l_0={ 1/2}$. However, in this paper, we show that the law of large numbers fails for $Z_{ n,k_n}$ if $\limsup_{ n\to\infty}\frac{ k_n}{ n^{ 4/9}}=\infty$. Thus, the critical exponent, if it exists, must satisfy $l_0\in[{ 2/5},{ 4/9}]$.
Categories: math.PR math.CO