The Ulam-Hammersley problem for multiset permutations
Author:
Preprint
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,...,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.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Order of the Variance in the Discrete Hammersley Process with BoundariesJournal of Statistical Physics, 2019
- The Surprising Mathematics of Longest Increasing Subsequences2014
- Second class particles and cube root asymptotics for Hammersley’s processThe Annals of Probability, 2006
- Hammersley’s process with sources and sinksThe Annals of Probability, 2005
- On the distribution of the length of the longest increasing subsequence of random permutationsJournal of the American Mathematical Society, 1999
- Increasing sequences of independent points on the planar latticeThe Annals of Applied Probability, 1997
- Hammersley's interacting particle process and longest increasing subsequencesProbability Theory and Related Fields, 1995