We study the lengths of monotone subsequences for permutations drawn from the Mallows measure. The Mallows measure was introduced by Mallows in connection with ranking problems in statistics. Under this measure, the probability of a permutation @math is proportional to @math where @math is a positive parameter and @math is the number of inversions in @math . In our main result we show that when @math , the limiting distribution of the longest increasing subsequence (LIS) is Gaussian, answering an open question in [Bhatnagar and Peled, PTRF, 2015]. This is in contrast to the case when @math where the limiting distribution of the LIS when scaled appropriately is the GUE Tracy-Widom distribution. We also obtain a law of large numbers for the length of the longest decreasing subsequence (LDS) and identify the precise constant in the order of the expectation, answering a further open question in [Bhatnagar and Peled, PTRF, 2015].
The case @math is special because it is one of the exactly solvable models that belong to the so-called KPZ universality class. In this case, the longest increasing subsequence problem can also be represented as a directed last passage percolation problem in a Poissonian environment. The results of @cite_23 @cite_12 follow from an asymptotic analysis of exact formulae that can be obtained for @math through a combinatorial bijection between @math and Young tableaux known as the Robinson-Schensted-Knuth (RSK) bijection @cite_4 @cite_33 @cite_6 . The RSK bijection can be further used to obtain the order of fluctuations and scaling limit of @math in this case. In their breakthrough work, Baik, Deift and Johansson showed that for uniformly random permutations @math has fluctuations of the order of @math and the limiting distribution of @math is the GUE Tracy-Widom distribution from random matrix theory @cite_2 .
@cite_4 @cite_33 @cite_6 @cite_23 @cite_2 @cite_12
89912732 2014678176 1691157804 2107037617
In this chapter we construct all the irreducible representations of the symmetric group. We know that the number of such representations is equal to the number of conjugacy classes (Proposition 1.10.1), which in the case of S n is the number of partitions of n. It may not be obvious how to associate an irreducible with each partition λ = (λ1, λ2,...., λl), but it is easy to find a corresponding subgroup S λ that is an isomorphic copy of S λl x Sλ2 x · · · x S λl, inside S n . We can now produce the right number of representations by inducing the trivial representation on each Sλ up to S n . This paper deals with finite sequences of integers. Typical of the problems we shall treat is the determination of the number of sequences of length n, consisting of the integers 1,2, ... , m, which have a longest increasing subsequence of length α. Throughout the first part of the paper we will deal only with sequences in which no numbers are repeated. In the second part we will extend the results to include the possibility of repetition. Our results will be stated in terms of standard Young tableaux. Let SN be the group of permutations of 1,2,..., N. If 7r E SN, we say that 7(i1),... , 7F(ik) is an increasing subsequence in 7r if il < i2 < ... < ik and 7r(ii) < 7r(i2) < ...< 7r(ik). Let 1N(r) be the length of the longest increasing subsequence. For example, if N = 5 and 7r is the permutation 5 1 3 2 4 (in one-line notation: thus 7r(1) = 5, 7r(2) = 1, ... ), then the longest increasing subsequences are 1 2 4 and 1 3 4, and N() = 3. Equip SN with uniform distribution, Abstract Stanley posed the problem of minimizing the functional H(f)= ∫ 0 ∞ dx ∫ 0 f(x) dy log (f (x) −y+f −1 (y) − x) over nonincreasing nonnegative f on (0, ∞) of integral unity. We show that the minimum is unique and has the value − 1 2 , as was conjectured by Stanley. The minimizing function f 0 , H(f 0 ) = − 1 2 , is given parametrically by f 0 (x)=( 2 π )(sin θ −θ cos θ), x =f o (x) + 2 cos θ, 0 ⩽ θ ⩽ π (2) for 0 ⩽ x ⩽ 2; and f 0 ( x ) = 0 for x ⩾ 2. Closely related unpublished results have been obtained by Hammersley. We also find the minimum of H ( f ) subject to the constraints f (0) ⩽ a and f −1 (0) = inf ( x : f ( x ) = 0) ⩽ b where a and b are given. Proofs of the results for the case of constraints are complicated and will be given elsewhere. Let λ n be the shape of the random Young tableau with n unit squares obtained from sampling from the Schensted distribution where P(λ n = n! π 2 (λ n ) (3) where π ( λ n ) is the product of the n hook lengths of λ n . Consider the stochastic processes λ n (t)=( 1 n 1 2 )λ(t n 1 2 , n ⩾ 1, t ⩾ 0 (4) where λ n ( t ) is the height of the tableau λ n at a horizontal distance t from the corner. We show λ n → f 0 in the sense of weak convergence in a certain metric, where f 0 is the deterministic function in (2). Let l ( σ n ) denote the length of the longest increasing subsequence of a random permutation σ n of 1,2,…, n . Hammersley showed that l(ω n ) n 1 2 →c in probability, n→∞ (6) Schensted showed that l ( σ n ) has the same distribution as λ n (0) under the distribution (3) on λ n . It has long been conjectured (apparently first by Baer and Brock) that c = 2. We show here that c ⩾ 2 as a by-product of (5).