The Ulam-Hammersley problem for multiset permutations

Lucas Gerin (1)

1 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique

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 generalizes the famous Ulam-Hammersley problem of the case k=1. The proof relies on poissonization and a connection with variants of the Hammersley-Aldous-Diaconis particle system.

Mots clés: combinatorial probability; longest increasing subsequence; Hammersley process; multiset permutations; Ulam's problem; Interacting particle system; discrete HAD process; HAD process

Domaines: Probabilités [math.PR]; Combinatoire [math.CO]

Lucas Gerin. The Ulam-Hammersley problem for multiset permutations. 2023. ⟨hal-03920072v4⟩