Record-biased permutations and their permuton limit
Combinatorics, Probability and Computing · 2026-05 · 35 (3) · 375-413
DOI: 10.1017/s0963548326100376 ↗Kurz gefasst
Fachartikel in der Zeitschrift Combinatorics, Probability and Computing, online erschienen am 27.03.2026. Verfasst von Mathilde Bouvel und 2 weiteren Autor:innen. Die Arbeit nennt 29 Literaturangaben.
Abstract (Originalsprache)
In this article, we study a non-uniform distribution on permutations biased by their number of records that we call record-biased permutations . We give several generative processes for record-biased permutations, explaining also how they can be used to devise efficient (linear) random samplers. For several classical permutation statistics, we obtain their expectation using the above generative processes, as well as their limit distributions in the regime that has a logarithmic number of records (as in the uniform case). Finally, increasing the bias to obtain a regime with an expected linear number of records, we establish the convergence of record-biased permutations to a deterministic permuton, which we fully characterise. This model was introduced in our earlier work [3], in the context of realistic analysis of algorithms. We conduct here a more thorough study but with a theoretical perspective.
Zitieren
APA
Bouvel, M., Nicaud, C., & Pivoteau, C. (2026). Record-biased permutations and their permuton limit. Combinatorics, Probability and Computing, 35(3), 375-413. https://doi.org/10.1017/s0963548326100376
Vancouver
Bouvel M, Nicaud C, Pivoteau C. Record-biased permutations and their permuton limit. Combinatorics, Probability and Computing. 2026;35(3):375-413. doi:10.1017/s0963548326100376
BibTeX
@article{Bouvel2026,
author = {Bouvel, Mathilde and Nicaud, Cyril and Pivoteau, Carine},
title = {Record-biased permutations and their permuton limit},
journal = {Combinatorics, Probability and Computing},
year = {2026},
volume = {35},
number = {3},
pages = {375--413},
doi = {10.1017/s0963548326100376}
}
EUVIMED