{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T05:46:28Z","timestamp":1778823988128,"version":"3.51.4"},"reference-count":38,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,12,19]],"date-time":"2014-12-19T00:00:00Z","timestamp":1418947200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2015,7]]},"abstract":"<jats:p>We show that for every sufficiently large<jats:italic>n<\/jats:italic>, the number of monotone subsequences of length four in a permutation on<jats:italic>n<\/jats:italic>points is at least<jats:disp-formula-group><jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548314000820_eqnU1\"\/><jats:tex-math>\\begin{equation*} \\binom{\\lfloor{n\/3}\\rfloor}{4} + \\binom{\\lfloor{(n+1)\/3}\\rfloor}{4} + \\binom{\\lfloor{(n+2)\/3}\\rfloor}{4}. \\end{equation*}<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>Furthermore, we characterize all permutations on [<jats:italic>n<\/jats:italic>] that attain this lower bound. The proof uses the flag algebra framework together with some additional stability arguments. This problem is equivalent to some specific type of edge colourings of complete graphs with two colours, where the number of monochromatic<jats:italic>K<\/jats:italic><jats:sub>4<\/jats:sub>is minimized. We show that all the extremal colourings must contain monochromatic<jats:italic>K<\/jats:italic><jats:sub>4<\/jats:sub>only in one of the two colours. This translates back to permutations, where all the monotone subsequences of length four are all either increasing, or decreasing only.<\/jats:p>","DOI":"10.1017\/s0963548314000820","type":"journal-article","created":{"date-parts":[[2014,12,19]],"date-time":"2014-12-19T11:13:34Z","timestamp":1418987614000},"page":"658-679","source":"Crossref","is-referenced-by-count":22,"title":["Minimum Number of Monotone Subsequences of Length 4 in Permutations"],"prefix":"10.1017","volume":"24","author":[{"given":"J\u00d3ZSEF","family":"BALOGH","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PING","family":"HU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BERNARD","family":"LIDICK\u00dd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"OLEG","family":"PIKHURKO","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BAL\u00c1ZS","family":"UDVARI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JAN","family":"VOLEC","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,12,19]]},"reference":[{"key":"S0963548314000820_ref38","unstructured":"Yamashita M. , Fujisawa K. , Nakata K. , Nakata M. , Fukuda M. , Kobayashi K. and Goto K. (2010) A high-performance software package for semidefinite programs: SDPA 7. Research Report B-460 Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Tokyo, Japan, September, 2010."},{"key":"S0963548314000820_ref37","unstructured":"Vaughan E. R. (2013) Flagmatic: Version 2.0. http:\/\/www.flagmatic.org"},{"key":"S0963548314000820_ref31","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21707"},{"key":"S0963548314000820_ref29","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1203350785"},{"key":"S0963548314000820_ref28","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511902499.015"},{"key":"S0963548314000820_ref27","doi-asserted-by":"crossref","first-page":"R50","DOI":"10.37236\/774","article-title":"Determining lower bounds for packing densities of non-layered patterns using weighted templates","volume":"15","author":"Presutti","year":"2008","journal-title":"Electron. J. Combin."},{"key":"S0963548314000820_ref25","unstructured":"Pikhurko O. and Razborov A. Asymptotic structure of graphs with the minimum number of triangles. arXiv:1204.2846. Submitted."},{"key":"S0963548314000820_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.03.006"},{"key":"S0963548314000820_ref22","doi-asserted-by":"crossref","first-page":"R4","DOI":"10.37236\/1676","article-title":"The minimum number of monotone subsequences","volume":"9","author":"Myers","year":"2002","journal-title":"Electron. J. Combin."},{"key":"S0963548314000820_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000612"},{"key":"S0963548314000820_ref19","first-page":"621","volume-title":"European Conference on Combinatorics, Graph Theory and Applications: EuroComb 2009","author":"Hladk\u00fd","year":"2009"},{"key":"S0963548314000820_ref35","unstructured":"Stein W. et al. (2013) Sage Mathematics Software: Version 5.6. The SAGE Development Team. http:\/\/www.sagemath.org"},{"key":"S0963548314000820_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000107"},{"key":"S0963548314000820_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.04.001"},{"key":"S0963548314000820_ref15","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1959.11989408"},{"key":"S0963548314000820_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000508"},{"key":"S0963548314000820_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9419-3"},{"key":"S0963548314000820_ref32","unstructured":"Samotij W. and Sudakov B. On the number of monotone sequences. Submitted."},{"key":"S0963548314000820_ref23","unstructured":"Nie\u00df S. Counting monochromatic copies of K 4: A new lower bound for the Ramsey multiplicity problem. Submitted."},{"key":"S0963548314000820_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2012.12.008"},{"key":"S0963548314000820_ref26","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548313000357"},{"key":"S0963548314000820_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.02.003"},{"key":"S0963548314000820_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.06.003"},{"key":"S0963548314000820_ref6","doi-asserted-by":"publisher","DOI":"10.1137\/130926614"},{"key":"S0963548314000820_ref34","unstructured":"Sperfeld K. (2011) On the minimal monochromatic K 4-density."},{"key":"S0963548314000820_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000222"},{"key":"S0963548314000820_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-88-7642-475-5_1"},{"key":"S0963548314000820_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90016-9"},{"key":"S0963548314000820_ref33","unstructured":"Sperfeld K. The inducibility of small oriented graphs. Submitted."},{"key":"S0963548314000820_ref11","first-page":"463","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u0151s","year":"1935","journal-title":"Compositio Math."},{"key":"S0963548314000820_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-7254-4_16"},{"key":"S0963548314000820_ref1","doi-asserted-by":"crossref","first-page":"R5","DOI":"10.37236\/1622","article-title":"On packing densities of permutations","volume":"9","author":"Albert","year":"2002","journal-title":"Electron. J. Combin."},{"key":"S0963548314000820_ref36","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-39.2.246"},{"key":"S0963548314000820_ref2","doi-asserted-by":"publisher","DOI":"10.1137\/06064888X"},{"key":"S0963548314000820_ref3","unstructured":"Baber R. Tur\u00e1n densities of hypercubes. Submitted."},{"key":"S0963548314000820_ref4","unstructured":"Baber R. (2011) Some results in extremal combinatorics. Dissertation."},{"key":"S0963548314000820_ref8","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805765"},{"key":"S0963548314000820_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.05.002"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000820","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,28]],"date-time":"2020-08-28T02:40:17Z","timestamp":1598582417000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000820\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,19]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,7]]}},"alternative-id":["S0963548314000820"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000820","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,19]]}}}