The Length of the Longest Increasing Subsequence of a Random Mallows Permutation

Abstract

The Mallows measure on the symmetric group $S_n$ is the probability measure such that each permutation has probability proportional to $q$ raised to the power of the number of inversions, where $q$ is a positive parameter and the number of inversions of $\pi$ is equal to the number of pairs $i<j$ such that ${\pi }_i>{\pi }_j$. We prove a weak law of large numbers for the length of the longest increasing subsequence for Mallows distributed random permutations, in the limit that $n$ tends to infinity and $q$ tends to 1 in such a way that $n(1-q)$ has a limit in $\mathbb{R}$.

References in corpus (1)

• Thermodynamic Limit for the Mallows Model on $S_n$