CaltechAUTHORS
  A Caltech Library Service

On longest increasing subsequences in random permutations

Odlyzko, A. M. and Rains, E. M. (2000) On longest increasing subsequences in random permutations. In: Analysis, Geometry, Number Theory: The Mathematics of Leon Ehrenpreis. Contemporary Mathematics. No.251. American Mathematical Society , Providence, RI, pp. 439-451. ISBN 978-0-8218-1148-1. http://resolver.caltech.edu/CaltechAUTHORS:20171009-160133131

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20171009-160133131

Abstract

The expected value of L_n, the length of the longest increasing subsequence of a random permutation of {1, ... , n}, has been studied extensively. This paper presents the results of both Monte Carlo and exact computations that explore the finer structure of the distribution of L_n. The results suggested that several of the conjectures that had been made about L_n were incorrect, and led to new conjectures, some of which have been proved recently by Jinho Baik, Percy Deift, and Kurt Johansson. In particular, the standard deviation of L_n is of order n^(1/6), contrary to earlier conjectures. This paper also explains some regular patterns in the distribution of L_n.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1090/conm/251/03886DOIArticle
http://www.ams.org/books/conm/251/3886/conm251-3886.pdfPublisherArticle
Additional Information:© 2000 American Mathematical Society. We thank Craig Tracy for providing the numerical data about asymptotic distribution of L_n that is used in Table 1 and Figure 1 and Jim Reeds for help with the random number generator programs. We also thank David Aldous, Harry Kesten, Anatoly Vershik, and Ofer Zeitouni for their comments.
Record Number:CaltechAUTHORS:20171009-160133131
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20171009-160133131
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:82239
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:09 Oct 2017 23:16
Last Modified:09 Oct 2017 23:16

Repository Staff Only: item control page