On increasing subsequences of random permutations
Let \(L_n\) be the length of a longest increasing subsequence in a random permutation of \(1,2,\dots,n\). Further let \(E[L_n]\) and \(V[L_n]\) be the expected value and the variance of \(L_n\), respectively. It is well known that \((2-o(1))\sqrt n\leq E[L_n]\leq 2\sqrt n\). By some recent results of M. Talagrand, B. Bollobás and J. Janson, we have \(c_1n^{1/8}\leq V[L_n]\leq c_2n^{1/2}\). In this paper the author proves that \(L_n-2\sqrt n\) is at most order \(n^{1/6}\) with high probability, which suggests that \(V[L_n]\) might be \(n^{1/3}\). Moreover, the author conjectures that \(cn^{1/3}\leq V[L_n]\leq c'n^{1/3}\) for some positive constants \(c\) and \(c'\).
- The longest increasing subsequence in a random permutation and a unitary random matrix model
- The height of a random partial order: Concentration of measure
- Monotonic subsequences in permutations of n natural numbers
- Longest increasing subsequences of random colored permutations
- The distribution of increasing l-sequences in random permutations: A Markov chain approach
- A note on the expected length of the longest common subsequences of two i.i.d. random permutations
- Catalan continued fractions and increasing subsequences in permutations
- Moderate deviations for longest increasing subsequences: The lower tail
- Perturbation of the equilibrium for a totally asymmetric stick process in one dimension
- Fractional moments of the stochastic heat equation
- When the law of large numbers fails for increasing subsequences of random permutations
- Large deviation rate functions for the partition function in a log-gamma distributed random potential
- A concentration bound for the longest increasing subsequence of a randomly chosen involution
- On the distribution of the length of the longest increasing subsequence in a random permutation
- The expected variation of random bounded integer sequences of finite length
- Continuously increasing subsequences of random multiset permutations
- Random permutations and the discrete Bessel kernel
- Law of large numbers for increasing subsequences of random permutations
- On the distribution of the length of the longest increasing subsequence of random permutations
- Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
- scientific article; zbMATH DE number 1047715 (Why is no real title available?)
- scientific article; zbMATH DE number 1515819 (Why is no real title available?)
- On increasing subsequences of minimal Erdős-Szekeres permutations
- Moderate deviations for longest increasing subsequences: The upper tail
- Optimal online selection of a monotone subsequence: a central limit theorem
- A Note on Sequential Selection from Permutations
- The corner growth model with exponential weights
- Increasing subsequences of random walks
- scientific article; zbMATH DE number 5204618 (Why is no real title available?)
- The Variance and the Asymptotic Distribution of the Length of Longest $k$-alternating Subsequences
- Continuously increasing subsequences of random multiset permutations
- Locally uniform random permutations with large increasing subsequences
- Random partial orders defined by angular domains
- Hydrodynamic large deviations of TASEP
- Descending subsequences of random permutations
This page was built for publication: On increasing subsequences of random permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1924244)
