Skip to content
DraconiticResearch
Search Sources API
186,541 studies31 sourcesUpdated 47 min ago
PreprintCC BY 4.0HAL

The longest increasing subsequences of Luce permutations and permutons

  • Jacopo Borga
  • Victor Dubach
Open at sourcePDFDOICite

Abstract

We investigate the longest increasing subsequences (LIS) of random permutations distributed under the Luce model with weights θ1(n) ≥ … ≥ θ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 √n. We also give simple conditions for the LIS to be of order nβ, for any given β∈[1/2,1). Our second main result states that, if the weights are of the form θk(n) = f( (k−1)/n ) for a sufficiently regular function f, then the LIS divided by 2√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''.

Related

  1. Longest increasing subsequences of dyadic-type chaotic orbits
    Shinsuke Iwao, Fumihiko Nakamura, Yushi Nakano
    arXivPreprintCC BY-SA 4.0Full textCombinatorics & discrete mathematicsDynamical systemsarXiv
  2. Recurrences for permutations with long increasing subsequences
    Manuel Kauers, Chen Wang
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Caged subsequences in permutations
    Niranjan Balachandran, Omkar Ramdas, Umesh Shankar
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Log-concavity of longest increasing subsequence
    Yupeng Li
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  5. On Chen's conjecture for the log-concavity of the longest increasing subsequence distribution
    Ernest X. W. Xia
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{borga2026longest,
  title = {{The longest increasing subsequences of Luce permutations and permutons}},
  author = {Jacopo Borga and Victor Dubach},
  howpublished = {HAL},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.30382},
  eprint = {2610.30382},
  archivePrefix = {arXiv},
  url = {https://hal.science/hal-05837644v1},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The longest increasing subsequences of Luce permutations and permutons
AU  - Jacopo Borga
AU  - Victor Dubach
PY  - 2026
DA  - 2026/10/21
PB  - HAL
DO  - 10.48550/arxiv.2610.30382
UR  - https://hal.science/hal-05837644v1
AB  - We investigate the longest increasing subsequences (LIS) of random permutations distributed under the Luce model with weights θ_1^(n) ≥ … ≥ θ_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 √n. We also give simple conditions for the LIS to be of order n^β, for any given β∈[1/2,1). Our second main result states that, if the weights are of the form θ_k^(n) = f( (k−1)/n ) for a sufficiently regular function f, then the LIS divided by 2√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''.
ER  -