No CrossRef data available.
Article contents
The Ulam–Hammersley problem for multiset permutations
Published online by Cambridge University Press: 09 May 2024
Abstract
We obtain the asymptotic behaviour of the longest increasing/non-decreasing subsequences in a random uniform multiset permutation in which each element in $\{1,\dots,n\}$ occurs k times, where k may depend on n. This generalises the famous Ulam–Hammersley problem of the case
$k=1$. The proof relies on poissonisation and on a careful non-asymptotic analysis of variants of the Hammersley–Aldous–Diaconis particle system.
MSC classification
- Type
- Research Article
- Information
- Copyright
- © The Author(s), 2024. Published by Cambridge University Press on behalf of Cambridge Philosophical Society
References
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20240508141209272-0933:S0305004124000124:S0305004124000124_inline487.png?pub-status=live)