\magnification=1200
\hsize=4in
\overfullrule=0pt
\nopagenumbers
\noindent
%
%
{\bf Joseph Samuel Myers}
%
%
\medskip
\noindent
%
%
{\bf The Minimum Number of Monotone Subsequences}
%
%
\vskip 5mm
\noindent
%
%
%
%
Erd\H{o}s and Szekeres showed that any permutation of length~$n \geq
k^2+1$ contains a monotone subsequence of length~$k+1$. A simple
example shows that there need be no more than $(n \bmod
k){{\lceil n/k \rceil}\choose {k+1}} + (k - (n \bmod k)){{\lfloor n/k
\rfloor}\choose {k+1}}$ such subsequences; we conjecture that this is the
minimum number of such subsequences. We prove this for~$k=2$, with a
complete characterisation of the extremal permutations. For $k > 2$
and $n \geq k(2k-1)$, we characterise the permutations containing the
minimum number of monotone subsequences of length~$k+1$ subject to the
additional constraint that all such subsequences go in the same
direction (all ascending or all descending); we show that there are $2
{{k}\choose {n \bmod k}} C_k^{2k-2}$~such extremal permutations, where
$C_k = {{1}\over {k+1}}{{2k}\choose {k}}$ is the $k^{{\rm th}}$~Catalan
number. We conjecture, with some supporting computational evidence,
that permutations with a minimum number of monotone
$(k+1)$-subsequences must have all such subsequences in the same
direction if $n \geq k(2k-1)$, except for the case of $k = 3$~and~$n =
16$.
\bye