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

الأصل · EN

Let the random variable Zₙ,ₖ denote the number of increasing subsequences of length k in a random permutation from Sₙ, 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ₙ,ₖₙ if kₙ=o(n²/⁵); that is, ₙ→∞Zₙ,ₖₙEZₙ,ₖₙ=1 in probability. The method of proof employed there used the second moment method and demonstrated that this method cannot work if the condition kₙ=o(n²/⁵) 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ₙ,ₖₙ if kₙ≥ cn¹/², with c>2. Presumably there is a critical exponent l₀ such that the law of large numbers holds if kₙ=O(nˡ), with l<l₀, and does not hold if ₙ→∞kₙ/nˡ>0, for some l>l₀. Several phase transitions concerning increasing subsequences occur at l=1/2, and these would suggest that l₀=1/2. However, in this paper, we show that the law of large numbers fails for Zₙ,ₖₙ if ₙ→∞kₙn⁴/⁹=∞. Thus, the critical exponent, if it exists, must satisfy l₀∈[2/5,4/9].