Longest increasing subsequences in pattern-restricted permutations (Q1871367): Difference between revisions

Summary: Inspired by the results of \textit{J. Baik, P. Deift} and \textit{K. Johansson} [J. Am. Math. Soc. 12, 1119-1178 (1999; Zbl 0932.05001)] on the limiting distribution of the lengths of the longest increasing subsequences in random permutations, we find those limiting distributions for pattern-restricted permutations in which the pattern is any one of the six patterns of length 3. We show that the (132)-avoiding case is identical to the distribution of heights of ordered trees, and that the (321)-avoiding case has interesting connections with a well-known theorem of \textit{P. Erdős} and \textit{G. Szekeres} [Compos. Math. 2, 463-470 (1935; Zbl 0012.27010 and JFM 61.0651.04)].