On increasing subsequences of random permutations
type: Item
instance of: scholarly article
title: On increasing subsequences of random permutations
zbMATH Open document ID: 0859.05002
author: Jeong Han Kim
published in: Journal of Combinatorial Theory. Series A
publication date: 1997-04-07T00:00:00Z
review text: 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'\).
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 934998
zbMATH Keywords: longest increasing subsequence
zbMATH Keywords: random permutation
zbMATH Keywords: variance
zbMATH Keywords: probability
reviewed by: Le Maohua
MaRDI profile type: Publication
OpenAlex ID: W2069679066
DOI: 10.1006/JCTA.1996.0095
description: scientific article; zbMATH DE number 934998