The Ulam-Hammersley problem for multiset permutations
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910904562483200 |
|---|---|
| author | Gerin, Lucas |
| author_facet | Gerin, Lucas |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_02557 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Ulam-Hammersley problem for multiset permutations Gerin, Lucas Combinatorics Probability 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. |
| title | The Ulam-Hammersley problem for multiset permutations |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2301.02557 |