Lengths of Monotone Subsequences in a Mallows Permutation 
Abstract: The longest increasing subsequence (LIS) of a uniformly random permutation is a well studied problem. VershikKerov and LoganShepp first showed that asymptotically the typical length of the LIS is 2sqrt(n). This line of research culminated in the work of BaikDeiftJohansson who related this length to the TracyWidom distribution. We study the length of the LIS and LDS of random permutations drawn from the Mallows measure, introduced by Mallows in connection with ranking problems in statistics. Under this measure, the probability of a permutation p in S_n is proportional to q^Inv(p) where q is a real parameter and Inv(p) is the number of inversions in p. We determine the typical order of magnitude of the LIS and LDS, large deviation bounds for these lengths and a law of large numbers for the LIS for various regimes of the parameter q. This is joint work with Ron Peled. 

Web page: Alexandru I. Suciu  Comments to: i.loseu@neu.edu  
Posted: October 19, 2014  URL: http://www.math.neu.edu/bhmn/Bhatnagar14.html 