|
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, 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.
|
