Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-15T22:41:14.134Z Has data issue: false hasContentIssue false

The Ulam–Hammersley problem for multiset permutations

Published online by Cambridge University Press:  09 May 2024

LUCAS GERIN*
Affiliation:
CMAP, CNRS, École Polytechnique, 91120 Palaiseau, France. e-mail: gerin@cmap.polytechnique.fr
Rights & Permissions [Opens in a new window]

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.

Information

Type
Research Article
Copyright
© The Author(s), 2024. Published by Cambridge University Press on behalf of Cambridge Philosophical Society
Figure 0

Fig. 1.A uniform 5-multiset permutation $S_{5;30}$ of size $n=30$ and one of its longest non-decreasing subsequences.

Figure 1

Fig. 2.The event F: a subsequence with $\delta\sqrt{n}$ (ties are surrounded) is depicted with $\times$’s.

Figure 2

Fig. 3.Our four variants of the Hammersley process (time goes from bottom to top). Top left: the process $L_\lt (t)$. Top right: the process $L_\leq (t)$. Bottom left: the process $L^{(\alpha,p)}_{\lt }(t)$. Bottom right: the process $L^{(\beta,\beta^\star)}_{\leq }(t)$.

Figure 3

Fig. 4.A sample of the process H.

Figure 4

Fig. 5.A sample of $\Pi^{(\lambda)}_{x,t}$, sources, sinks, and the corresponding trajectories of particles. Here $\mathcal{L}_{=\lt }(\Pi^{(\lambda)}_{x,t}\cup \textsf{So}^{(\alpha)}_x\cup \textsf{Si}^{(p)}_t)=5$ and $L^{(\alpha,p)}_{\lt }(t)=2$ (two remaining particles at the top of the box).

Figure 5

Fig. 6.Illustration of the notation of Lemma 14. Top: the multiset permutation $S_{k;n}$. Bottom: the corresponding $\widetilde{S}$. The longest non-decreasing subsequence in $S_{k;n}$ (circled points) is mapped onto a non-decreasing subsequence in $\widetilde{S}$, except one point with height $\gt A\lfloor n/A\rfloor$.

Figure 6

Fig. B1.Notation of Lemma 18. Points of $\overline{\Pi}$ are depicted with $\star$’s.