The longest increasing subsequences of Luce permutations and permutons
In the authors' words
We investigate the longest increasing subsequences (LIS) of random permutations distributed under the Luce model with weights . 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 grows like . We also give simple conditions for the LIS to be of order , for any given . Our second main result states that, if the weights are of the form for a sufficiently regular function , then the LIS divided by converges in probability to a constant 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".
Appeared: Friday, October 23. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 28 pages. Comments welcome!