{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T13:46:27Z","timestamp":1767015987199},"reference-count":10,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T00:00:00Z","timestamp":1692316800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T00:00:00Z","timestamp":1692316800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ELKH Alfr\u00e9d R\u00e9nyi Institute of Mathematics"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2023,12]]},"abstract":"Abstract<\/jats:title>The systematic study of Tur\u00e1n-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. (Tur\u00e1n problems for Edge-ordered graphs, 2021). They conjectured that the extremal functions of edge-ordered forests of order chromatic number 2 are $$n^{1+o(1)}$$<\/jats:tex-math>\n \n n<\/mml:mi>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Here we resolve this conjecture proving the stronger upper bound of $$n2^{O(\\sqrt{\\log n})}$$<\/jats:tex-math>\n \n n<\/mml:mi>\n \n 2<\/mml:mn>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \n log<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This represents a gap in the family of possible extremal functions as other forbidden edge-ordered graphs have extremal functions $$\\Omega (n^c)$$<\/jats:tex-math>\n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n c<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for some $$c>1$$<\/jats:tex-math>\n \n c<\/mml:mi>\n ><\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. However, our result is probably not the last word: here we conjecture that the even stronger upper bound of $$n\\log ^{O(1)}n$$<\/jats:tex-math>\n \n n<\/mml:mi>\n \n log<\/mml:mo>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> also holds for the same set of extremal functions.<\/jats:p>","DOI":"10.1007\/s00493-023-00052-5","type":"journal-article","created":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T07:02:49Z","timestamp":1692342169000},"page":"1111-1123","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Characterization of Edge-Ordered Graphs with Almost Linear Extremal Functions"],"prefix":"10.1007","volume":"43","author":[{"given":"Gaurav","family":"Kucheriya","sequence":"first","affiliation":[]},{"given":"G\u00e1bor","family":"Tardos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,18]]},"reference":[{"key":"52_CR1","unstructured":"Erd\u0151s, P.: Extremal problems in graph theory. In: Proceedings of Symposium on Graph Theory, Smolenice, Acad. C.S.S.R., 1963, pp. 29\u201336 (1963)"},{"key":"52_CR2","first-page":"51","volume":"1","author":"P Erd\u0151s","year":"1966","unstructured":"Erd\u0151s, P., Simonovits, M.: A limit theorem in graph theory. Stud. Sci. Math. Hung. 1, 51\u201357 (1966)","journal-title":"Stud. Sci. Math. Hung."},{"key":"52_CR3","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1090\/S0002-9904-1946-08715-7","volume":"52","author":"P Erd\u0151s","year":"1946","unstructured":"Erd\u0151s, P., Stone, A.H.: On the structure of linear graphs. Bull. Am. Math. Soc. 52, 1087\u20131091 (1946)","journal-title":"Bull. Am. Math. Soc."},{"key":"52_CR4","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0012-365X(92)90316-8","volume":"103","author":"Z F\u00fcredi","year":"1992","unstructured":"F\u00fcredi, Z., Hajnal, P.: Davenport\u2013Schinzel theory of matrices. Discrete Math. 103, 233\u2013251 (1992)","journal-title":"Discrete Math."},{"key":"52_CR5","unstructured":"Gerbner, D., Methuku, A., Nagy, D., P\u00e1lv\u00f6lgyi, D., Tardos, G., Vizer, M.: Tur\u00e1n problems for Edge-ordered graphs (2021) arXiv:2001.00849"},{"key":"52_CR6","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.jcta.2019.01.006","volume":"165","author":"D Kor\u00e1ndi","year":"2019","unstructured":"Kor\u00e1ndi, D., Tardos, G., Tomon, I., Weidert, C.: On the Tur\u00e1n number of ordered forests. J. Comb. Theory A 165, 32\u201343 (2019)","journal-title":"J. Comb. Theory A"},{"key":"52_CR7","doi-asserted-by":"crossref","unstructured":"Kucheriya, G., Tardos, G.: On edge-ordered graphs with linear extremal functions, manuscript (2022)","DOI":"10.1007\/s00493-023-00052-5"},{"key":"52_CR8","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1006\/jctb.1994.1020","volume":"60","author":"F Lazebnik","year":"1994","unstructured":"Lazebnik, F., Ustimenko, V.A., Woldar, A.J.: Properties of certain families of $$2k$$-cycle-free graphs. J. Comb. Theory B 60, 293\u2013298 (1994)","journal-title":"J. Comb. Theory B"},{"key":"52_CR9","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF02773960","volume":"155","author":"J Pach","year":"2006","unstructured":"Pach, J., Tardos, G.: Forbidden paths and cycles in ordered graphs and matrices. Isr. J. Math. 155, 359\u2013380 (2006)","journal-title":"Isr. J. Math."},{"key":"52_CR10","doi-asserted-by":"publisher","first-page":"2396","DOI":"10.1016\/j.disc.2011.06.020","volume":"311","author":"S Pettie","year":"2011","unstructured":"Pettie, S.: Degrees of nonlinearity in forbidden 0\u20131 matrix problems. Discrete Math. 311, 2396\u20132410 (2011)","journal-title":"Discrete Math."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00052-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-023-00052-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00052-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,24]],"date-time":"2023-11-24T14:03:52Z","timestamp":1700834632000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-023-00052-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,18]]},"references-count":10,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["52"],"URL":"https:\/\/doi.org\/10.1007\/s00493-023-00052-5","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,18]]},"assertion":[{"value":"28 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}