The longest increasing subsequences of Luce permutations and permutons

We investigate the longest increasing subsequences (LIS) of random permutations distributed under the Luce model with weights ${\theta }_1^{(n)}\ge \dots \ge {\theta }_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 ${\theta }_k^{(n)}=n-k+1$ grows like $\sqrt{n}$. We also give simple conditions for the LIS to be of order $n^{\beta }$, for any given $\beta \in [1\mathrm{/}2,1)$. Our second main result states that, if the weights are of the form ${\theta }_k^{(n)}=f((k-1)\mathrm{/}n)$ 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’'.