{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T01:10:17Z","timestamp":1777425017808,"version":"3.51.4"},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2021,1,8]],"date-time":"2021-01-08T00:00:00Z","timestamp":1610064000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We prove a number of results related to a problem of Po-Shen Loh [9], which is equivalent to a problem in Ramsey theory. Let <jats:italic>a<\/jats:italic> = (<jats:italic>a<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>a<\/jats:italic><jats:sub>2<\/jats:sub>, <jats:italic>a<\/jats:italic><jats:sub>3<\/jats:sub>) and <jats:italic>b<\/jats:italic> = (<jats:italic>b<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>b<\/jats:italic><jats:sub>2<\/jats:sub>, <jats:italic>b<\/jats:italic><jats:sub>3<\/jats:sub>) be two triples of integers. Define <jats:italic>a<\/jats:italic> to be 2<jats:italic>-less than b<\/jats:italic> if <jats:italic>a<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub> &lt; <jats:italic>b<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub> for at least two values of <jats:italic>i<\/jats:italic>, and define a sequence <jats:italic>a<\/jats:italic><jats:sup>1<\/jats:sup>, \u2026, <jats:italic>a<\/jats:italic><jats:sup><jats:italic>m<\/jats:italic><\/jats:sup> of triples to be 2<jats:italic>-increasing<\/jats:italic> if <jats:italic>a<\/jats:italic><jats:sup><jats:italic>r<\/jats:italic><\/jats:sup> is 2-less than <jats:italic>a<\/jats:italic><jats:sup><jats:italic>s<\/jats:italic><\/jats:sup> whenever <jats:italic>r<\/jats:italic> &lt; <jats:italic>s<\/jats:italic>. Loh asks how long a 2-increasing sequence can be if all the triples take values in {1, 2, \u2026, <jats:italic>n<\/jats:italic>}, and gives a log<jats:sub>*<\/jats:sub> improvement over the trivial upper bound of <jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup> by using the triangle removal lemma. In the other direction, a simple construction gives a lower bound of <jats:italic>n<\/jats:italic><jats:sup>3\/2<\/jats:sup>. We look at this problem and a collection of generalizations, improving some of the known bounds, pointing out connections to other well-known problems in extremal combinatorics, and asking a number of further questions.<\/jats:p>","DOI":"10.1017\/s0963548320000371","type":"journal-article","created":{"date-parts":[[2021,1,8]],"date-time":"2021-01-08T13:01:41Z","timestamp":1610110901000},"page":"686-721","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":7,"title":["The length of an <i>s<\/i>-increasing sequence of <i>r<\/i>-tuples"],"prefix":"10.1017","volume":"30","author":[{"given":"W. T.","family":"Gowers","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Long","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,1,8]]},"reference":[{"key":"S0963548320000371_ref8","unstructured":"[8] Gowers, W. T. Bipartite graphs of approximate rank one. https:\/\/www.dpmms.cam.ac.uk\/\u02dcwtg10\/approxrankone3.pdf"},{"key":"S0963548320000371_ref1","doi-asserted-by":"publisher","DOI":"10.37236\/7224"},{"key":"S0963548320000371_ref2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.32.12.331"},{"key":"S0963548320000371_ref9","unstructured":"[9] Loh, P. (2015) Directed paths: from Ramsey to Ruzsa and Szemer\u00e9di. To appear in Combin. Probab. Comput. arXiv:1505.07312"},{"key":"S0963548320000371_ref15","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1967.22.523"},{"key":"S0963548320000371_ref10","first-page":"258","article-title":"Extensions of the linear bound in the F\u00fcredi\u2013Hajnal conjecture","volume":"38","author":"Marcus","year":"2006","journal-title":"Adv. Appl. Math"},{"key":"S0963548320000371_ref4","first-page":"55","volume-title":"New Directions in the Theory of Graphs","author":"Brown","year":"1973"},{"key":"S0963548320000371_ref12","doi-asserted-by":"publisher","DOI":"10.4064\/aa-65-3-259-282"},{"key":"S0963548320000371_ref17","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/BF03024896","article-title":"Packing tripods","volume":"17","author":"Stein","year":"1995","journal-title":"Math. Intelligencer"},{"key":"S0963548320000371_ref3","volume-title":"Combinatorics; Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability","author":"Bollob\u00e1s","year":"1986"},{"key":"S0963548320000371_ref6","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2011.174.1.17"},{"key":"S0963548320000371_ref19","unstructured":"[19] Tidor, J. , Wang, V. Y. and Yang, B. (2016) 1-color-avoiding paths, special tournaments, and incidence geometry. arXiv:1608.04153"},{"key":"S0963548320000371_ref13","first-page":"939","article-title":"Triple systems with no six points carrying three triangles","volume":"18","author":"Ruzsa","year":"1978","journal-title":"Coll. Math. Soc. J. Bolyai"},{"key":"S0963548320000371_ref21","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22117"},{"key":"S0963548320000371_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2004.12.028"},{"key":"S0963548320000371_ref16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1984.1056880"},{"key":"S0963548320000371_ref5","doi-asserted-by":"publisher","DOI":"10.1090\/noti1421"},{"key":"S0963548320000371_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.04.002"},{"key":"S0963548320000371_ref18","doi-asserted-by":"publisher","DOI":"10.5948\/UPO9781614440246"},{"key":"S0963548320000371_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90316-8"},{"key":"S0963548320000371_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0006-6"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000371","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,6]],"date-time":"2021-08-06T13:37:11Z","timestamp":1628257031000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000371\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,8]]},"references-count":21,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["S0963548320000371"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000371","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,8]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}