\documentclass[12pt,dvips,times]{article} \usepackage{epsfig,psfig} \pagestyle{myheadings} \markright{\sc Monotonic subsequences, \#R14\hfill} \thispagestyle{empty} \input amssym.def \input amssym.tex \input psfig \setlength{\textwidth}{6in} \setlength{\textheight}{9in} \setlength{\topmargin}{-0.25in} \newtheorem{lemma}{Lemma}[section] \newtheorem{theorem}{Theorem}[section] \newtheorem{prop}{Proposition}[section] \newcommand{\hsp}{\hspace*{\parindent}} \newcommand{\RR}{{\Bbb R}} \newcommand{\ZZ}{{\Bbb Z}} \newcommand{\eeq}{\end{equation}} \newcommand{\beql}[1]{\begin{equation}\label{#1}} \newcommand{\eqn}[1]{(\ref{#1})} \def\binom#1#2{{#1}\choose{#2}} \makeatletter % put a period after section or subsection number in header \def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2>\c@secnumdepth \def\@svsec{}\else \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em }\fi \@tempskipa #5\relax \ifdim \@tempskipa>\z@ \begingroup #6\relax \@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}% \endgroup \csname #1mark\endcsname{#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}\else \def\@svsechd{#6\hskip #3\@svsec #8\csname #1mark\endcsname {#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}}\fi \@xsect{#5}} % put a period after theorem and theorem-like numbers \def\section{\@startsection {section}{1}{\z@}{-2.5ex plus -1ex minus -.1ex}{1.3ex plus .2ex}{\large\bf}} \makeatother \renewcommand{\theequation}{\arabic{section}.\arabic{equation}} \catcode`\@=11 \renewcommand{\section}{ \setcounter{equation}{0} \@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus -.2ex}{2.3ex plus .2ex}{\large\bf} } \catcode`@=12 \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 4 (no. 2) (1997), \#R14\hfill} \thispagestyle{empty} \thispagestyle{empty} \begin{document} \begin{center} {\Large\bf Monotonic subsequences in dimensions \\ higher than one} \\ \vspace*{1.5\baselineskip} {\em A. M. Odlyzko} \\ AT\&T Labs - Research \\ Murray Hill, NJ 07974 \\ email: amo@research.att.com \\ \vspace*{1\baselineskip} {\em J. B. Shearer} \\ IBM T. J. Watson Research Center \\ P.O. Box 218 \\ Yorktown Heights, NY 10598 \\ email: jbs@watson.ibm.com \\ \vspace*{1\baselineskip} {\em R. Siders} \\ AT\&T Labs - Research \\ Murray Hill, NJ 07974 \\ email: siders@math.umn.edu \\ \vspace*{1.5\baselineskip} {\em Dedicated to Herb Wilf on the occasion of his 65-th birthday} \\ \vspace*{1\baselineskip} Submitted: August 31, 1996; Accepted: November 10, 1996 \\ \vspace*{1.5\baselineskip} {\bf Abstract} \end{center} %\setlength{\baselineskip}{1.5\baselineskip} The 1935 result of Erd\H{o}s and Szekeres that any sequence of $\ge n^2 +1$ real numbers contains a monotonic subsequence of $\ge n+1$ terms has stimulated extensive further research, including a paper of J.~B. Kruskal that defined an extension of monotonicity for higher dimensions. This paper provides a proof of a weakened form of Kruskal's conjecture for 2-dimensional Euclidean space by showing that there exist sequences of $n$ points in the plane for which the longest monotonic subsequences have length $\le n^{1/2} +3$. Weaker results are obtained for higher dimensions. When points are selected at random from reasonable distributions, the average length of the longest monotonic subsequence is shown to be $\sim 2n^{1/2}$ as $n \to \infty$ for each dimension. \\ \vspace*{1.25in} \noindent AMS-MOS Subject Classification: Primary: 05A05, Secondary: 06A07, 60C05. \clearpage %\large\normalsize %\renewcommand{\baselinestretch}{1} \thispagestyle{empty} \setcounter{page}{1} \begin{center} {\Large\bf Monotonic subsequences in dimensions \\ higher than one} \\ \vspace*{1.5\baselineskip} {\em A. M. Odlyzko} \\ AT\&T Labs - Research \\ Murray Hill, NJ 07974 \\ email: amo@research.att.com \\ \vspace*{1\baselineskip} {\em J. B. Shearer} \\ IBM T. J. Watson Research Center \\ Yorktown Heights, NY 10598 \\ email: jbs@watson.ibm.com \\ \vspace*{1\baselineskip} {\em R. Siders} \\ AT\&T Labs - Research \\ Murray Hill, NJ 07974 \\ email: siders@math.umn.edu \\ \vspace*{1.5\baselineskip} {\em Dedicated to Herb Wilf on the occasion of his 65-th birthday} \\ \vspace*{1\baselineskip} \end{center} %\setlength{\baselineskip}{1.5\baselineskip} \section{Introduction} \hsp A sequence $y_1 , \ldots, y_k$ of real numbers is said to be {\em monotonic} if either $y_1 \le y_2 \le \cdots \le y_k$ or $y_1 \ge y_2 \ge \cdots \ge y_k$. A classic theorem of Erd\H{o}s and Szekeres \cite{ES} states that every sequence of $m^2 +1$ real numbers has a monotonic subsequence of $m+1$ terms. Moreover, there do exist sequences of $m^2$ real numbers with no monotonic subsequences of length greater than $m$. This extremal result has led to research on a range of related problems in both extremal and average behavior. For references, see the survey of Mike Steele \cite{Steele2}, and \cite{OdlyzkoR}. The result of Erd\H{o}s and Szekeres stimulated the question of what happens when in a sequence $x_1 , \ldots, x_n$, the real numbers $x_j$ are replaced by vectors $x_j$ from $d$-dimensional Euclidean space. The first problem is to define what is meant by monotonicity for a subsequence in dimension $d \ge 2$. One way to do this is to say that a subsequence $x_{i_1} , \ldots, x_{i_k}$, $1 \le i_1 < \cdots < i_k \le n$, is monotonic if it is monotonic in each coordinate (when the $x_j$ are presented in some fixed coordinate system). N.~G. de~Bruijn showed (see \cite{Kruskal}) that for this definition, a complete answer can be obtained from the Erd\H{o}s-Szekeres result. From a sequence of $m^{2^d} +1$ vectors in $\RR^d$, a monotonic subsequence of $m+1$ terms can be chosen, and this is best possible. A different generalization to higher dimensions, this time to relation spaces, was considered by J.~B. Kruskal \cite{Kruskal}. In this case he was also able to obtain a complete answer using the Erd\H{o}s-Szekeres result. In this note we consider yet another generalization of monotonicity to vectors in $\RR^d$ that was proposed by Kruskal in \cite{Kruskal}. It is more natural geometrically than the one considered by de~Bruijn in that it is independent of the choice of the coordinate system. There are several definitions (all shown to be equivalent to each other in \cite{Kruskal}). The one we will work with says that a sequence $y_1, \ldots, y_k$, with $y_j \in \RR^d$ for each $j$, is monotonic if there exists some nonzero $w \in \RR^d$ such that the sequence of inner products $(y_1, w) , \ldots, (y_k , w)$ is a monotonic sequence of real numbers. With this definition of monotonicity, any sequence of $d+1$ points is monotonic. Also, since any nonzero $w$ can be chosen, it is immediate by the Erd\H{o}s-Szekeres result \cite{ES} that a monotonic subsequence of $\ge \lceil n^{1/2} \rceil$ points can be chosen from any sequence of $n$ points. Kruskal conjectured that to guarantee the existence of a monotonic subsequence of length $k \ge d+1$, it is necessary and sufficient that the total number of points $n$ satisfy $n \ge k^2 - kd - k+d+1$. If Kruskal's conjecture is true, then for every $d$, there will be sequences of points in $\RR^d$ with longest monotonic subsequences of length $(1+ o(1))n^{1/2}$ as $n \to \infty$. As an aside, suppose we take $y_1, \ldots, y_n$ to be any of the sequences that are extremal for the Erd\H{o}s-Szekeres result, so that the $y_j$ are real numbers, and the longest monotonic subsequence among them has length $\lceil n^{1/2} \rceil$. Let us now construct a sequence in $\RR^d$ by placing the $y_j$ on a line, say $x_j = (y_j, 0, \ldots, 0)$ for $1 \le j \le n$. Then for any $w \in \RR^d$ with nonzero first coordinate, the longest monotonic subsequence of $(x_1, w) , \ldots, (x_n,w)$ will have length $\lceil n^{1/2} \rceil$. However, for $w= (0,1, 0, \ldots, 0)$, we will have $(x_j,w)=0$ for all $j$, so for this $w$ we will obtain a monotonic subsequence of length $n$. This shows that if we required strict monotonicity for the subsequences of the $(x_j,w)$, the problem would have a trivial solution. We will show in Section~2 that if $d$ is fixed and $z_1, \ldots, z_n$ are any $n$ points in $\RR^d$ that are in general position, then as $n \to \infty$, almost all permutations $x_1, \ldots, x_n$ of $z_1, \ldots, z_n$ will have their longest monotonic subsequence of length $(2+ o(1))n^{1/2}$ as $n \to \infty$. In particular, if the $z_j$ are chosen independently at random from some continuous distribution on $\RR^d$ (say uniform on the unit cube), and are permuted at random, then we will get maximal monotonic subsequences of length $(2+o(1)) n^{1/2}$ as $n \to \infty$ with high probability. Since most random choices give longest monotonic subsequences not much longer than $2n^{1/2}$ for any $d \ge 2$, we get (asymptotically for $n \to \infty$) within a factor of 2 of what Kruskal's conjecture predicts. However, that is the most that this method can do for us. On the other hand, in Section~3 we present an explicit construction of a sequence in $d=2$ for which the longest monotonic subsequence has length $\le n^{1/2} + 3$. This shows that for $d=2$ Kruskal's conjecture is asymptotically tight. We expect that similar although more complicated constructions exist for all $d \ge 3$, and therefore that the asymptotic form of Kruskal's conjecture is true for all dimensions. We do not know whether the exact form of Kruskal's conjecture is correct. For $d=2$, we can improve our bound to $\le n^{1/2} + 2$, but we do not know whether our construction can be modified to give the full conjecture. \section{Average behavior} \hsp Ulam \cite{Ulam} was apparently the first one to ask about the distribution of $L_n$, the length of the longest increasing subsequence in a permutation of $n$ distinct real numbers. After initial work of Baer and Brock \cite{BaerB} and Hammersley \cite{Ham}, Logan and Shepp \cite{LoganS} and Vershik and Kerov \cite{VershikK} proved the conjecture that $L_n$ tends to $2n^{1/2}$ in probability as $n \to \infty$. Later it was shown by Frieze \cite{Frieze} that the distribution of $L_n$ is concentrated near its mean. Frieze's result was subsequently sharpened by Bollob\'{a}s and Brightwell \cite{BB} and Talagrand \cite{Tala}. Some of the fine structure details of the distribution of $L_n$ are still unknown. For full references, numerical evidence, and conjectures about the distribution of $L_n$, see \cite{OdlyzkoPWW} and \cite{OdlyzkoR}. In this paper we will use only two results. One follows from the lower bound of Logan and Shepp and of Vershik and Kerov: \begin{prop} \label{pr21} For every $\epsilon > 0$, \beql{eq21} {\rm Prob} (L_n > (2- \epsilon) n^{1/2} ) \to 1 \quad \mbox{as} \quad n \to \infty ~. \eeq \end{prop} The other result is a weak form of the upper bound that follows from the work of Frieze, of Bollob\'{a}s and Brightwell, and of Talagrand. The result we will actually use follows also from the one-sided concentration result of J.-H. Kim \cite{Kim}, which is simpler to prove, but yields surprisingly strong bounds. (We will use only a weak version of Kim's result.) \begin{prop}\label{pr22} For all $\alpha , \epsilon > 0$, there is a constant $C = C( \alpha, \epsilon)$ such that \beql{eq22} {\rm Prob} ( L_n > (2+ \epsilon ) n^{1/2} ) \le Cn^{- \alpha} ~. \eeq \end{prop} Let us now consider points $z_1, \ldots, z_n \in \RR^d$ that are in general position (no 3 on a line, no 4 in a plane, etc.). For any nonzero $w \in \RR^d$, permuting the $z_j$ induces a permutation of the inner products $(z_j,w)$. Hence Proposition~\ref{pr21} shows immediately that if we permute the $z_j$, the resulting sequences $x_1, \ldots, x_n$ will almost always have monotonic subsequences of length $\ge (2+ o(1)) n^{1/2}$ as $n \to \infty$. Suppose again that $z_1, \ldots, z_n \in \RR^d$ are in general position, and suppose that $x_1, \ldots, x_n$ is a permutation of $z_1, \ldots, z_n$. In determining monotonicity of subsequences of $x_1, \ldots, x_n$, we only need to consider directions $w$ that satisfy $d-1$ linearly independent constraints of the form $(w, z_i - z_j ) =0$. (Suppose we move $w$ continuously without hitting any additional conditions $(w, z_i ) = (w, z_j)$, and without destroying any conditions of this type that held before. Then the relative positions of the $(w, z_i )$ do not change, and when we do add an additional relation $(w, z_i) = (w, z_j )$, longest monotone subsequences can only grow.) However, there are fewer than ${\binom{n}{2}}^{d-1}$ such directions $w$. For each $w$, a random permutation of $z_1, \ldots , z_n$ gives a random permutation of the $n-2 (d-1)$ numbers $(w, z_j )$ for which $(w, z_j)$ is unique. We apply Proposition~\ref{pr22} to those, and conclude that the probability of a monotone subsequence of length $\ge (2+ \epsilon )n^{1/2}+ 2d$ is $\le n^{-10d}$ for $n$ sufficiently large. Hence the probability of a monotone subsequence of length $\ge (2+ \epsilon )n^{1/2} + 2d$ for any of the $\le n^{2d}$ directions $w$ that need to be considered is $o(1)$ as $n \to \infty$. Combining the results proved above, we obtain the following result. \begin{theorem}\label{th21} If $z_1, \ldots, z_n \in \RR^d$ are in general position, and are permuted at random, then for any $\epsilon > 0$, the length $M_n$ of the longest monotonic subsequence in the permuted sequence satisfies \beql{eq23} {\rm Prob} ((2- \epsilon )n^{1/2} \le M_n \le (2+ \epsilon )n^{1/2} ) \to 1 \quad \mbox{as} \quad n \to \infty ~. \eeq \end{theorem} The restriction to general positions in Theorem~\ref{th21} is important, since $z_1 = z_2 = \cdots = z_n =0$ produces dramatically different behavior. Theorem~\ref{th21} determines the typical asymptotic behavior of the length of the longest monotonic subsequence in $\RR^d$. The same methods can also be used to study the expected lengths of unimodal and related subsequences, if those notions are extended to $\RR^d$ in the same way. (For $d=1$, these questions were answered by Chung \cite{Chung} and Steele \cite{Steele1}.) \section{Extremal sequences} \hsp Section~2 showed that for any $d \ge 2$, there do exist sequences $x_1 , \ldots, x_n \in \RR^d$ with longest monotonic subsequences of length $(2+ o(1))n^{1/2}$ as $n \to \infty$. That is within a factor of 2 of what Kruskal's conjecture predicts. In this section we show that for $d=2$, we can construct sequences of points that gain that factor of 2, and so come close to proving Kruskal's conjecture. (Our construction yields sequences that in which the longest monotonic subsequences are longer by at most 2 than those predicted to exist by Kruskal's conjecture. A careful examination of our proof shows that we can decrease our upper bound by 1, and thus be at most 1 worse than Kruskal's conjecture.) \begin{theorem}\label{th3} For any $n \in \ZZ^+$, there exists a sequence of points $x_1, \ldots, x_n \in \RR^2$ which has no monotonic subsequence of length $> \lfloor n^{1/2} \rfloor +2$. \end{theorem} \paragraph{Proof.} We first use induction to construct, for all $k \in \ZZ^+$ and $0 < \epsilon < 1/10$, a sequence of points $z_1, \ldots, z_k \in \RR^2$ with the following properties: \begin{itemize} \item[(i)] the angle between any two lines determined by pairs of the $z_j$ is $< \epsilon$. \item[(ii)] If the line through $z_1$ and $z_k$ is turned in a counterclockwise direction, the projections of the $z_j$ on that line appear first in the order $$z_1 , z_2, \ldots, z_k ~.$$ Then, as the line keeps turning, $z_1$ moves past $z_2$, so the order becomes $$z_2, z_1 , z_3 , \ldots, z_k ~.$$ Then $z_1$ moves past $z_3 , \ldots, z_k$, in turn, while the order of those points remains unchanged, until the order becomes $$z_2, z_3, \ldots, z_k, z_1 ~.$$ Next, as the line continues turning, $z_k$ moves past $z_{k-1}$, then past $z_{k-2}, \ldots$, and finally $z_2$ to create the order of projections $$z_k , z_2, z_3, \ldots, z_{k-1} , z_1 ~.$$ Next, $z_2$ moves past $z_3$, then $z_4, \ldots$, until the order is $$z_k, z_3, z_4, \ldots, z_{k-1} , z_2, z_1 ~,$$ and then $z_{k-1}$ starts moving past $z_{k-2} , \ldots$~. In the end, when the rotation reaches 180$^\circ$, we see the reversed order $$z_k , z_{k-1} , \ldots, z_2, z_1 ~.$$ \item[(iii)] If we look at the points $z_j$ in the order $z_1, z_k , z_2, z_{k-1} , z_3 , z_{k-2} , \ldots$, then any point $z_j$ lies inside the triangle determined by the preceding three points in this ordering. \end{itemize} To start the induction, for $k=1$ we choose $z_1$ to be a point, for $k=2$ let $z_1$ and $z_2$ be any two distinct points, and for $k=3$ let $z_1$, $z_2$, and $z_3$ be the three points in Fig.~1 that are labeled $z_1$, $z_2$, and $z_k$, respectively. Suppose that we can construct $I(k-2, \epsilon ')$ for any $0 < \epsilon ' < 1/10$. We next proceed to construct $I(k, \epsilon )$ for any $\epsilon$ with $0 < \epsilon < 1/10$ as follows. Let $z_1 = (0,0)$, $z_k = (4,0)$, and scale and translate $I(k-2 , \epsilon /1000 )$ so that if its points are $z'_1 , \ldots, z'_{k-2}$, then $$z'_1 = (2, - \epsilon / 10 ) , ~~~ z'_{k-2} = (3, - 49 \epsilon / 1000) ~.$$ (See Fig.~1 for this construction.) If we then let $z_j = z'_{j-1}$, $2 \le j \le k-1$, we easily see that the sequence $z_1$, $z_2, \ldots, z_k$ satisfies all the conditions for $I(k, \epsilon )$. \begin{figure}[htb] \centerline{\psfig{file=mo2.ps,width=3.5in}\vspace*{.3in}} \caption{Construction of points $z_1, z_2, \ldots, z_k$.} \end{figure} We now proceed to prove Theorem~\ref{th3}. It suffices to construct a sequence $x_1, \ldots, x_n$ satisfying the conditions of this theorem for $n=m^2$. Let $z_1, \ldots, z_n$ be the sequence of points $I(n, 1/100)$ constructed above. We now rearrange them into the sequence $x_1, \ldots, x_n$. To do this, we write the numbers $1,2, \ldots, n$ into a regular diamond with 1 on top, 2 and 3 beneath it (in that order, although any ordering of this or other rows would do just as well), 4, 5, and 6 beneath them, and so on, until we get $n$ in the bottom row. (See Fig.~2 for $n=16$.) \begin{figure}[htb] $$ \begin{array}{rrrrrrr} ~ & ~ & ~ & 1 \\ [+.1in] ~ & ~ & 2 & ~ & 3 \\ [+.1in] ~ & 4 & ~ & 5 & ~ & 6 \\ [+.1in] 7 & ~ & 8 & ~ & 9 & ~ & 10 \\ [+.1in] ~ & 11 & ~ & 12 & ~ & 13 \\ [+.1in] ~ & ~ & 14 & ~ & 15 & \\ [+.1in] ~ & ~ & ~ & 16 \end{array} $$ \caption{Diamond configuration for $n=16$, used to define the sequence $x_1, \ldots, x_{16}$.} \end{figure} Read the points left to right, reading the columns from top to bottom for the column headed by 1 and all the columns to the left of that one, and reading the columns to the right of the central one from bottom to top. For the case $n=16$ illustrated in Fig.~2, we obtain the ordering \beql{eq31} 7, 4, 11, 2, 8, 14, 1, 5, 12, 16, 15, 9, 3, 13, 6, 10 ~. \eeq In general, if the sequence is $s_1, \ldots, s_n$, we define $z_j = x_{s_j}$ for $1 \le j \le n$. (For $n=16$, we have $z_1 = x_7$, $z_2 = x_4$, $z_3 = x_{11}$, and so one.) We now look at projections of the $x_j$ onto a line that rotates counterclockwise, and starts parallel to the $x$-axis. We first examine just those directions for which the projections of the $z_j$ in that direction have the ordering \beql{eq32} z_n , z_{n-1} , \ldots, z_{n-t} , z_{t+2} , z_{t+3} , \ldots, z_{n-t-2} , z_{n-t-1} , z_{t+1} , z_t , \ldots, z_2, z_1 ~. \eeq The ordering of the projections of the $x_j$ is obtained from the same diamond we started with, but after interchanging the $t+1$ extreme pairs of points in the initial ordering. For example, for $n=16$ and $t=3$, we interchange the pairs of labels $(7,10)$, $(4,6)$, $(11,13)$, and $(2,3)$ in the diamond of Fig.~2. (See Fig.~3 for an illustration.) \begin{figure}[htb] $$ \begin{array}{rrrrrrr} ~ & ~ & ~ & 1 \\ [+.1in] ~ & ~ & 3 & ~ & 2 \\ [+.1in] ~ & 6 & ~ & 5 & ~ & 4 \\ [+.1in] 10 & ~ & 8 & ~ & 9 & ~ & 7 \\ [+.1in] ~ & 13 & ~ & 12 & ~ & 11 \\ [+.1in] ~ & ~ & 14 & ~ & 15 \\ [+.1in] ~ & ~ & ~ & 16 \end{array} $$ \caption{Diamond configuration for $n=16$ and $t=3$.} \end{figure} The interchanges in the diamond always involve pairs of points in the same row (except when at the end we interchange points inside the central column, first $1$ with $n$, then 5 with $n-4$, and so on). Hence an increasing subsequence of projections must move to the right or down in the diamond, and so has at most $m= n^{1/2}$ elements. Similarly, a decreasing subsequence has to move left or up, and so also has at most $m$ elements. It remains to consider projections intermediate between those that give arrangements of the form \eqn{eq32}. However, these projections differ from those given by \eqn{eq32} in the positioning of at most two points. Hence any monotonic subsequence of our sequence has length $\le m+2 = n^{1/2} +2$.~\hfill~QED \begin{thebibliography}{SchenstedM} \bibitem{BaerB} R.~M. Baer and P. Brock, Natural sorting over permutation spaces, {\em Math. Comp. 22} (1968), 385--410. \bibitem{BB} B. Bollob\'{a}s and G. Brightwell, The height of a random partial order: concentration of measure, {\em Ann. Appl. Prob. 2} (1992), 1009--1018. \bibitem{Chung} F.~R.~K. Chung, On unimodal subsequences, {\em J. Comb. Theory A~29} (1980), 267--279. \bibitem{ES} P. Erd\H{o}s and G. Szekeres, A combinatorial theorem in geometry, {\em Compositio Math. 2} (1935), 463-470. \bibitem{Frieze} A. Frieze, On the length of the longest monotone subsequence in a random permutation, {\em Ann. Appl. Prob. 1} (1991), 301--305. \bibitem{Ham} J.~M. Hammersley, A few seedlings of research, pp.~345--394 in {\em Proc. 6th Berkeley Symp. Math. Stat. Prob.}, Univ. California Press, 1972. \bibitem{Kim} J.-H. Kim, On the longest increasing subsequences of random permutations - a concentration result, {\em J. Comb. Th. A 76} (1996), 148--155. \bibitem{Kruskal} J.~B. Kruskal, Monotonic subsequences, {\em Proc. Amer. Math. Soc. 4} (1953), 264-274. \bibitem{LoganS} B.~F. Logan and L.~A. Shepp, A variational problem for random Young tableaux, {\em Advances Math. 26} (1977), 206--222. \bibitem{OdlyzkoPWW} A.~M. Odlyzko, B. Poonen, H. Widom, and H.~S. Wilf, On the distribution of longest increasing subsequences in random permutations, in preparation. \bibitem{OdlyzkoR} A.~M. Odlyzko and E.~M. Rains, On longest increasing subsequences in random permutations, to be published. \bibitem{Steele1} J.~M. Steele, Long unimodal subsequences: A problem of F.~R.~K. Chung, {\em Discrete Math. 33} (1981), 223--225. \bibitem{Steele2} J.~M. Steele, Variations on the monotone subsequence theme of Erd\H{o}s and Szekeres, pp. 111-131 in {\em Discrete Probability and Algorithms}, D. Aldous, P. Diaconis, J. Spencer, and J.~M. Steele, eds., Springer, 1995. \bibitem{Tala} M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, {\em Publ. Math. Inst. Hautes Etud. Sci. 81} (1995), 73-205. \bibitem{Ulam} S.~M. Ulam, Monte Carlo calculations in problems of mathematical physics, pp.~261--281 in {\em Modern Mathematics for the Engineer}, E.~F. Beckenbach, ed., McGraw-Hill, 1961. \bibitem{VershikK} A.~M. Vershik and C.~V. Kerov, Asymptotics of the Plancheral measure of the symmetric group and a limiting form for Young tableaux, {\em Dokl. Akad. Nauk USSR, 233} (1977), 1024--1027. (In Russian.) \end{thebibliography} \end{document}