no. 5 · Friday 30 October 2026
The longest increasing subsequences of Luce permutations and permutons
Abstract
We investigate the longest increasing subsequences (LIS) of random permutations distributed under the Luce model with weights $θ_1^{(n)} \ge \ldots \ge θ_n^{(n)}$. Our first main result provides a general formula for the growth rate of the LIS. For example, we get that the LIS of Luce permutations with Sukhatme weights $θ_k^{(n)} = n-k+1$ grows like $\sqrt{n}$. We also give simple conditions for the LIS to be of order $n^β$, for any given $β\in[1/2,1)$. Our second main result states that, if the weights are of the form $θ_k^{(n)} = f\big( (k-1)/n \big)$ for a sufficiently regular function $f$, then the LIS divided by $2\sqrt{n}$ converges in probability to a constant $K(f)$ described by a variational problem. Throughout, we make extensive use of coupling techniques; in particular, to prove our second main result, we argue that Luce random permutations behave similarly to random permutations sampled from the ``Luce permuton''.
- comments
- 29 pages. v2: minor changes in the introduction
- fields
- Probability, Combinatorics