pipette
ESEspañol

The longest increasing subsequences of Luce permutations and permutons

Jacopo Borga, Victor Dubach

Preprint

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

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 23. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 28 pages. Comments welcome!