Locally uniform random permutations with large increasing subsequences
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909432473976832 |
|---|---|
| author | Dubach, Victor |
| author_facet | Dubach, Victor |
| contents | We investigate the maximal size of an increasing subset among points randomly sampled from certain probability densities. Kerov and Vershik's celebrated result states that the largest increasing subset among $N$ uniformly random points on $[0,1]^2$ has size asymptotically $2\sqrt{N}$. More generally, the order $Θ(\sqrt{N})$ still holds if the sampling density is continuous. In this paper we exhibit two sufficient conditions on the density to obtain a growth rate equivalent to any given power of $N$ greater than $\sqrt{N}$, up to logarithmic factors. Our proofs use methods of slicing the unit square into appropriate grids, and investigating sampled points appearing in each box. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_07658 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Locally uniform random permutations with large increasing subsequences Dubach, Victor Probability Combinatorics 60C05, 05A05 We investigate the maximal size of an increasing subset among points randomly sampled from certain probability densities. Kerov and Vershik's celebrated result states that the largest increasing subset among $N$ uniformly random points on $[0,1]^2$ has size asymptotically $2\sqrt{N}$. More generally, the order $Θ(\sqrt{N})$ still holds if the sampling density is continuous. In this paper we exhibit two sufficient conditions on the density to obtain a growth rate equivalent to any given power of $N$ greater than $\sqrt{N}$, up to logarithmic factors. Our proofs use methods of slicing the unit square into appropriate grids, and investigating sampled points appearing in each box. |
| title | Locally uniform random permutations with large increasing subsequences |
| topic | Probability Combinatorics 60C05, 05A05 |
| url | https://arxiv.org/abs/2301.07658 |