Library

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

Bayesian Methods and Mixture ModelsRandom Matrices and ApplicationsLimits and Structures in Graph Theory
Source

Paper

Similar papers

Locally uniform random permutations with large increasing subsequencesVictor Dubach2023 · Combinatorial Theory In Library
A Chinese restaurant process for multiset permutationsDudley Stark2026 · Modern Stochastics Theory and Applications In Library
A Chinese restaurant process for multiset permutationsDudley Stark2025 · arXiv (Cornell University) In Library
Longest subsequence for certain repeated up/down patterns in random permutations avoiding a pattern of length threeRoss G. Pinsky2024 · arXiv (Cornell University) In Library
A Central Limit Theorem for Repeating PatternsAaron Abrams, Eric Babson, H. G. Landau et al.2026 · The Electronic Journal of Combinatorics In Library
An Alternative Proof for the Expected Number of Distinct Consecutive Patterns in a Random PermutationAnant P. Godbole, Hannah Swickheimer2023 · arXiv (Cornell University) In Library
Clustering of consecutive numbers in permutations avoiding a pattern and\n in separable permutationsRoss G. Pinsky2021 · arXiv (Cornell University) In Library
Monotone Subsequences in Locally Uniform Random PermutationsJonas Sjöstrand2022 · arXiv (Cornell University) In Library
The proportion of permutations fixing a $k$-setBen Green, Mehtaab Sawhney2026 · arXiv (Cornell University) In Library
The Variance and the Asymptotic Distribution of the Length of Longest $k$-alternating SubsequencesAltar Çiçeksiz, Yunus Emre Demirci, Ümi̇t Işlak2021 · arXiv (Cornell University) In Library
© 2026 NYSGPT2525 LLC