Nayantara Bhatnagar
University of Delaware
Title: Lengths of Monotone Subsequences in a Mallows Permutation

Abstract: The longest increasing subsequence (LIS) of a uniformly random permutation is a well studied problem. Vershik- Kerov and Logan-Shepp first showed that asymptotically the typical length of the LIS is 2sqrt(n). This line of research culminated in the work of Baik-Deift-Johansson who related this length to the Tracy-Widom distribution. We study the length of the LIS and LDS of random permutations drawn from the Mallows measure. Under this measure, the probability of a permutation p in Sn is proportional to q^Inv(p) where q is a real parameter and Inv(p) is the number of inversions in p. The Mallows measure was introduced by Mallows in connection with ranking problems in statistics.

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. We also show that in the graphical representation of a Mallows-distributed permutation, most points are found in a symmetric strip around the diagonal whose width is of order 1/(1-q). Finally, we prove some simple preliminary bounds on the variance of these lengths.

This is joint work with Ron Peled.

©2013, Department of Mathematical Sciences
Last Modified: March 18, 2013