  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}]$.
