The Ulam–Hammersley problem for multiset permutations

We obtain the asymptotic behaviour of the longest increasing/non-decreasing subsequences in a random uniform multiset permutation in which each element in \1,,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.