{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:10Z","timestamp":1753893790187,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>Erd\u0151s 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 &gt; 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$.<\/jats:p>","DOI":"10.37236\/1676","type":"journal-article","created":{"date-parts":[[2020,1,11]],"date-time":"2020-01-11T02:23:42Z","timestamp":1578709422000},"source":"Crossref","is-referenced-by-count":8,"title":["The Minimum Number of Monotone Subsequences"],"prefix":"10.37236","volume":"9","author":[{"given":"Joseph Samuel","family":"Myers","sequence":"first","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2002,12,13]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v9i2r4\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v9i2r4\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,18]],"date-time":"2020-01-18T05:10:39Z","timestamp":1579324239000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v9i2r4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,12,13]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2002,10,31]]}},"URL":"https:\/\/doi.org\/10.37236\/1676","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2002,12,13]]},"article-number":"R4"}}