{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T04:18:37Z","timestamp":1772252317150,"version":"3.50.1"},"reference-count":8,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2019,11,7]],"date-time":"2019-11-07T00:00:00Z","timestamp":1573084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>As a kind of converse of the celebrated Erd\u0151s\u2013Szekeres theorem, we present a necessary and sufficient condition for a sequence of length n to contain a longest increasing subsequence and a longest decreasing subsequence of given lengths x and y, respectively.<\/jats:p>","DOI":"10.3390\/a12110237","type":"journal-article","created":{"date-parts":[[2019,11,7]],"date-time":"2019-11-07T06:52:36Z","timestamp":1573109556000},"page":"237","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["What Do a Longest Increasing Subsequence and a Longest Decreasing Subsequence Know about Each Other?"],"prefix":"10.3390","volume":"12","author":[{"given":"Elizabeth J.","family":"Itskovich","sequence":"first","affiliation":[{"name":"Department of Computer Science, Ariel University, Ariel 40700, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vadim E.","family":"Levit","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ariel University, Ariel 40700, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,11,7]]},"reference":[{"key":"ref_1","first-page":"463","article-title":"A combinatorial problem in geometry","volume":"2","author":"Szekeres","year":"1935","journal-title":"Compositio Mathematica"},{"key":"ref_2","unstructured":"Bukh, B., and Sevekari, A. (2019). Linear orderings of combinatorial cubes. arXiv, 9."},{"key":"ref_3","first-page":"135","article-title":"On Some Variants of the Longest Increasing Subsequence Problem","volume":"21","author":"Deorowich","year":"2009","journal-title":"Theor. Appl. Inform."},{"key":"ref_4","first-page":"A29","article-title":"Erd\u0151s-Szekeres results for set partitions","volume":"8","author":"Gottlieb","year":"2015","journal-title":"Integers 15"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Romik, D. (2015). The Surprising Mathematics of Longest Increasing Subsequences. Institute of Mathematical Statistics Textbooks, 4, Cambridge University Press.","DOI":"10.1017\/CBO9781139872003"},{"key":"ref_6","first-page":"545","article-title":"Increasing and decreasing subsequences and their variants","volume":"I","author":"Stanley","year":"2007","journal-title":"Int. Congr. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/978-1-4612-0801-3_9","article-title":"Variations on the monotone subsequence theme of Erd\u0151s and Szekeres","volume":"Volume 72","author":"Steele","year":"1995","journal-title":"IMA Volumes in Mathematics and Its Applications"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Xu, X., Liang, M., and Luo, H. (2018). Ramsey Theory: Unsolved Problems and Results, De Gruyter\/University of Science and Technology of China Press.","DOI":"10.1515\/9783110576702"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/11\/237\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:32:27Z","timestamp":1760189547000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/11\/237"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,7]]},"references-count":8,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2019,11]]}},"alternative-id":["a12110237"],"URL":"https:\/\/doi.org\/10.3390\/a12110237","relation":{"has-preprint":[{"id-type":"doi","id":"10.20944\/preprints201908.0247.v1","asserted-by":"object"}]},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,7]]}}}