{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T13:22:50Z","timestamp":1767014570245,"version":"3.48.0"},"reference-count":62,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T00:00:00Z","timestamp":1762473600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T00:00:00Z","timestamp":1762473600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,12]]},"abstract":"Abstract<\/jats:title>\n \n The theory of forbidden 0\u20131 matrices generalizes Tur\u00e1n-style (bipartite) subgraph avoidance, Davenport-Schinzel theory, and Zarankiewicz-type problems, and has been influential in many areas, such as discrete and computational geometry, the analysis of self-adjusting data structures, and the development of the graph parameter\n twin width<\/jats:italic>\n . The foremost open problem in this area is to resolve the\n Pach-Tardos conjecture<\/jats:italic>\n from 2005, which states that if a forbidden pattern\n \n \n $$P\\in \\{0,1\\}^{k\\times l}$$<\/jats:tex-math>\n \n \n P<\/mml:mi>\n \u2208<\/mml:mo>\n \n \n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n \n k<\/mml:mi>\n \u00d7<\/mml:mo>\n l<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is\n acyclic<\/jats:italic>\n , meaning it is the bipartite incidence matrix of a forest, then\n \n \n $$\\operatorname {Ex}(P,n) = O(n\\log ^{C_P} n)$$<\/jats:tex-math>\n \n \n Ex<\/mml:mo>\n \n (<\/mml:mo>\n P<\/mml:mi>\n ,<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n O<\/mml:mi>\n \n (<\/mml:mo>\n n<\/mml:mi>\n \n log<\/mml:mo>\n \n C<\/mml:mi>\n P<\/mml:mi>\n <\/mml:msub>\n <\/mml:msup>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , where\n \n \n $$\\operatorname {Ex}(P,n)$$<\/jats:tex-math>\n \n \n Ex<\/mml:mo>\n (<\/mml:mo>\n P<\/mml:mi>\n ,<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is the maximum number of 1s in a\n P<\/jats:italic>\n -free\n \n \n $$n\\times n$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \u00d7<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n 0\u20131 matrix and\n \n \n $$C_P$$<\/jats:tex-math>\n \n \n C<\/mml:mi>\n P<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is a constant depending only on\n P<\/jats:italic>\n . This conjecture has been confirmed on many small patterns, specifically all\n P<\/jats:italic>\n with weight at most 5, and all but two with weight 6. The main result of this paper is a clean refutation of the Pach-Tardos conjecture. Specifically, we prove that\n \n \n $$\\operatorname {Ex}(S_0,n),\\operatorname {Ex}(S_1,n) \\ge n2^{\\Omega (\\sqrt{\\log n})}$$<\/jats:tex-math>\n \n \n Ex<\/mml:mo>\n \n (<\/mml:mo>\n \n S<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n ,<\/mml:mo>\n Ex<\/mml:mo>\n \n (<\/mml:mo>\n \n S<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n n<\/mml:mi>\n \n 2<\/mml:mn>\n \n \u03a9<\/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>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , where\n \n \n $$S_0,S_1$$<\/jats:tex-math>\n \n \n \n S<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n S<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n are the outstanding weight-6 patterns. We also prove sharp bounds on the entire class of\n alternating<\/jats:italic>\n patterns\n \n \n $$(P_t)$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n \n P<\/mml:mi>\n t<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , specifically that for every\n \n \n $$t\\ge 2$$<\/jats:tex-math>\n \n \n t<\/mml:mi>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n \n \n $$\\operatorname {Ex}(P_t,n)=\\Theta (n(\\log n\/\\log \\log n)^t)$$<\/jats:tex-math>\n \n \n Ex<\/mml:mo>\n \n (<\/mml:mo>\n \n P<\/mml:mi>\n t<\/mml:mi>\n <\/mml:msub>\n ,<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \u0398<\/mml:mi>\n \n (<\/mml:mo>\n n<\/mml:mi>\n \n \n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n \/<\/mml:mo>\n log<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n t<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . This is the first proof of an asymptotically sharp bound that is\n \n \n $$\\omega (n\\log n)$$<\/jats:tex-math>\n \n \n \u03c9<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n .\n <\/jats:p>","DOI":"10.1007\/s00493-025-00187-7","type":"journal-article","created":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T11:38:01Z","timestamp":1762515481000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Refutation of the Pach-Tardos Conjecture for 0\u20131 Matrices"],"prefix":"10.1007","volume":"45","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[]},{"given":"G\u00e1bor","family":"Tardos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,11,7]]},"reference":[{"key":"187_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Fischer, N., Kelley, Z., Lovett, S., Meka, R.: New graph decompositions and combinatorial boolean matrix multiplication algorithms. In Proceedings 56th ACM Symposium on Theory of Computing (STOC) (2024)","DOI":"10.1145\/3618260.3649696"},{"key":"187_CR2","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1073\/pnas.32.12.331","volume":"32","author":"FA Behrend","year":"1946","unstructured":"Behrend, F.A.: On sets of integers which contain no three terms in arithmetic progression. Proc. Nat. Acad. Sci. 32, 331\u2013332 (1946)","journal-title":"Proc. Nat. Acad. Sci."},{"issue":"1","key":"187_CR3","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1137\/0404002","volume":"4","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D., Gy\u0151ri, E.: An extremal problem on sparse 0\u20131 matrices. SIAM J. Discr. Math. 4(1), 17\u201327 (1991)","journal-title":"SIAM J. Discr. Math."},{"key":"187_CR4","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Geniet, C., Kim, E.J., Thomass\u00e9, S., Watrigant, R.: Twin-width II: small classes. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1977\u20131996 (2021)","DOI":"10.1137\/1.9781611976465.118"},{"issue":"1","key":"187_CR5","doi-asserted-by":"crossref","first-page":"3:1","DOI":"10.1145\/3486655","volume":"69","author":"\u00c9 Bonnet","year":"2022","unstructured":"Bonnet, \u00c9., Kim, E.J., Thomass\u00e9, S., Watrigant, R.: Twin-width I: tractable FO model checking. J. ACM 69(1), 3:1-3:46 (2022)","journal-title":"J. ACM"},{"key":"187_CR6","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0095-8956(74)90052-5","volume":"16","author":"JA Bondy","year":"1974","unstructured":"Bondy, J.A., Simonovits, M.: Cycles of even length in graphs. J. Combinatorial Theory Ser. B 16, 97\u2013105 (1974)","journal-title":"J. Combinatorial Theory Ser. B"},{"issue":"1","key":"187_CR7","doi-asserted-by":"crossref","first-page":"15","DOI":"10.2140\/ent.2023.2.15","volume":"2","author":"TF Bloom","year":"2023","unstructured":"Bloom, T.F., Sisask, O.: The Kelley Meka bounds for sets free of three-term arithmetic progressions. Essential Number Theory 2(1), 15\u201344 (2023)","journal-title":"Essential Number Theory"},{"key":"187_CR8","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Gupta, M., Jiamjitrak, W., Acosta, N.O., Pareek, A., Yingchareonthawornchai, S.: Improved pattern-avoidance bounds for greedy BSTs via matrix decomposition. In Proceedings of the 34th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 509\u2013534 (2023)","DOI":"10.1137\/1.9781611977554.ch22"},{"key":"187_CR9","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Goswami, M., Kozma, L., Mehlhorn, K., Saranurak, T.: Greedy is an almost optimal deque. In Proceedings 14th Symposium on Algorithms and Data Structures, volume 9214 of Lecture Notes in Computer Science, pages 152\u2013165 (2015)","DOI":"10.1007\/978-3-319-21840-3_13"},{"key":"187_CR10","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Goswami, M., Kozma, L., Mehlhorn, K., Saranurak, T.: Pattern-avoiding access in binary search trees. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), pages 410\u2013423 (2015)","DOI":"10.1109\/FOCS.2015.32"},{"issue":"2","key":"187_CR11","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1016\/j.jcta.2008.06.003","volume":"116","author":"J Cibulka","year":"2009","unstructured":"Cibulka, J.: On constants in the F\u00fcredi-Hajnal and the Stanley-Wilf conjecture. J. Comb. Theory, Ser. A 116(2), 290\u2013302 (2009)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"187_CR12","doi-asserted-by":"crossref","unstructured":"Cibulka, J., Kyn\u010dl, J.: Better upper bounds on the F\u00fcredi-Hajnal limits of permutations. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2280\u20132293 (2017)","DOI":"10.1137\/1.9781611974782.150"},{"key":"187_CR13","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Pettie, S., Yingchareonthawornchai, S.: Sorting pattern-avoiding permutations via 0-1 matrices forbidding product patterns. In Proceedings 35th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 133\u2013149 (2024)","DOI":"10.1137\/1.9781611977912.7"},{"key":"187_CR14","doi-asserted-by":"crossref","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. Amer. Math. Soc. 52, 1087\u20131091 (1946)","journal-title":"Bull. Amer. Math. Soc."},{"key":"187_CR15","first-page":"51","volume":"1","author":"P Erd\u0151s","year":"1966","unstructured":"Erd\u0151s, P., Simonovits, M.: A limit theorem in graph theory. Studia Sci. Math. Hungar. 1, 51\u201357 (1966)","journal-title":"Studia Sci. Math. Hungar."},{"issue":"3","key":"187_CR16","doi-asserted-by":"crossref","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-Schinzel theory of matrices. Discret. Math. 103(3), 233\u2013251 (1992)","journal-title":"Discret. Math."},{"issue":"6","key":"187_CR17","doi-asserted-by":"crossref","first-page":"1648","DOI":"10.4153\/S0008414X20000632","volume":"73","author":"Z F\u00fcredi","year":"2021","unstructured":"F\u00fcredi, Z., Jiang, T., Kostochka, A., Mubayi, D., Verstra\u00ebte, J.: Extremal problems for convex geometric hypergraphs and ordered hypergraphs. Canadian J. Math. 73(6), 1648\u20131666 (2021)","journal-title":"Canadian J. Math."},{"issue":"2","key":"187_CR18","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1007\/s00454-019-00149-z","volume":"64","author":"Z F\u00fcredi","year":"2020","unstructured":"F\u00fcredi, Z., Kostochka, A.V., Mubayi, D., Verstra\u00ebte, J.: Ordered and convex geometric trees with linear extremal function. Discret. Comput. Geom. 64(2), 324\u2013338 (2020)","journal-title":"Discret. Comput. Geom."},{"key":"187_CR19","unstructured":"Fox, J.: Stanley-Wilf limits are typically exponential (2013). arXiv:1310.8378"},{"key":"187_CR20","doi-asserted-by":"crossref","unstructured":"F\u00fcredi, Z., Simonovits, M.: The history of degenerate (bipartite) extremal graph problems. In L\u00e1szl\u00f3 Lov\u00e1sz, Imre\u00a0Z. Ruzsa, and Vera\u00a0T. S\u00f3s, editors, Erd\u0151s Centennial, number\u00a025 in Bolyai Society Mathematical Studies, pages 169\u2013264. Springer, (2013)","DOI":"10.1007\/978-3-642-39286-3_7"},{"key":"187_CR21","doi-asserted-by":"crossref","first-page":"1736","DOI":"10.1016\/j.disc.2008.02.040","volume":"309","author":"R Fulek","year":"2009","unstructured":"Fulek, R.: Linear bound on extremal functions of some forbidden patterns in 0\u20131 matrices. Discret. Math. 309, 1736\u20131739 (2009)","journal-title":"Discret. Math."},{"issue":"2","key":"187_CR22","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1016\/0097-3165(90)90074-7","volume":"55","author":"Z F\u00fcredi","year":"1990","unstructured":"F\u00fcredi, Z.: The maximum number of unit distances in a convex $$n$$-gon. J. Combin. Theory Ser. A 55(2), 316\u2013320 (1990)","journal-title":"J. Combin. Theory Ser. A"},{"issue":"7","key":"187_CR23","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1016\/j.jcta.2009.03.004","volume":"116","author":"JT Geneson","year":"2009","unstructured":"Geneson, J.T.: Extremal functions of forbidden double permutation matrices. J. Combin. Theory Ser. A 116(7), 1235\u20131244 (2009)","journal-title":"J. Combin. Theory Ser. A"},{"key":"187_CR24","unstructured":"Geneson, J.T.: Bounds on extremal functions of forbidden patterns. PhD thesis, Massachusetts Institute of Technology, Department of Mathematics (2015)"},{"key":"187_CR25","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.ejc.2019.02.003","volume":"78","author":"JT Geneson","year":"2019","unstructured":"Geneson, J.T.: Forbidden formations in multidimensional 0\u20131 matrices. Eur. J. Comb. 78, 147\u2013154 (2019)","journal-title":"Eur. J. Comb."},{"key":"187_CR26","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/j.ejc.2018.05.008","volume":"73","author":"E Gy\u00f6ri","year":"2018","unstructured":"Gy\u00f6ri, E., Kor\u00e1ndi, D., Methuku, A., Tomon, I., Tompkins, C., Vizer, M.: On the Tur\u00e1n number of some ordered even cycles. Eur. J. Comb. 73, 81\u201388 (2018)","journal-title":"Eur. J. Comb."},{"key":"187_CR27","doi-asserted-by":"crossref","unstructured":"Guillemot, S., Marx, D.: Finding small patterns in permutations in linear time. In Proceedings 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 82\u2013101, (2014)","DOI":"10.1137\/1.9781611973402.7"},{"key":"187_CR28","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/j.jctb.2022.12.006","volume":"160","author":"D Gerbner","year":"2023","unstructured":"Gerbner, D., Methuku, A., Nagy, D.T., P\u00e1lv\u00f6lgyi, D., Tardos, G., Vizer, M.: Tur\u00e1n problems for edge-ordered graphs. J. Comb. Theory, Ser. B 160, 66\u2013113 (2023)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"12","key":"187_CR29","doi-asserted-by":"crossref","first-page":"2769","DOI":"10.1016\/j.disc.2017.08.017","volume":"340","author":"JT Geneson","year":"2017","unstructured":"Geneson, J.T., Tian, P.M.: Extremal functions of forbidden multidimensional matrices. Discret. Math. 340(12), 2769\u20132781 (2017)","journal-title":"Discret. Math."},{"issue":"4","key":"187_CR30","first-page":"4","volume":"27","author":"JT Geneson","year":"2020","unstructured":"Geneson, J.T., Tsai, S.-F.: Sharper bounds and structural results for minimally nonlinear 0\u20131 matrices. Electron. J. Comb. 27(4), 4 (2020)","journal-title":"Electron. J. Comb."},{"issue":"2","key":"187_CR31","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579170","volume":"6","author":"S Hart","year":"1986","unstructured":"Hart, S., Sharir, M.: Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. Combinatorica 6(2), 151\u2013177 (1986)","journal-title":"Combinatorica"},{"key":"187_CR32","doi-asserted-by":"crossref","unstructured":"Janzer, B., Janzer, O., Magnan, V., Methuku, A.: Tight general bounds for the extremal numbers of 0\u20131 matrices (2024). arXiv:2403.04728","DOI":"10.1093\/imrn\/rnae129"},{"issue":"1","key":"187_CR33","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1016\/j.jcta.2008.05.006","volume":"116","author":"B Keszegh","year":"2009","unstructured":"Keszegh, B.: On linear forbidden submatrices. J. Combin. Theory Ser. A 116(1), 232\u2013241 (2009)","journal-title":"J. Combin. Theory Ser. A"},{"issue":"4","key":"187_CR34","first-page":"737","volume":"33","author":"M Klazar","year":"1992","unstructured":"Klazar, M.: A general upper bound in extremal theory of sequences. Comment. Math. Univ. Carolin. 33(4), 737\u2013746 (1992)","journal-title":"Comment. Math. Univ. Carolin."},{"key":"187_CR35","doi-asserted-by":"crossref","unstructured":"Klazar, M.: The F\u00fcredi-Hajnal conjecture implies the Stanley-Wilf conjecture. In Formal power series and algebraic combinatorics (Moscow, 2000), pages 250\u2013255. Springer, Berlin (2000)","DOI":"10.1007\/978-3-662-04166-6_22"},{"key":"187_CR36","first-page":"A11","volume":"2","author":"M Klazar","year":"2002","unstructured":"Klazar, M.: Generalized Davenport-Schinzel sequences: results, problems, and applications. Integers 2, A11 (2002)","journal-title":"Integers"},{"key":"187_CR37","doi-asserted-by":"crossref","unstructured":"Kelley, Z., Meka, R.: Strong bounds for 3-progressions. In Proceedings 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 933\u2013973 (2023)","DOI":"10.1109\/FOCS57990.2023.00059"},{"key":"187_CR38","doi-asserted-by":"crossref","first-page":"1111","DOI":"10.1007\/s00493-023-00052-5","volume":"43","author":"G Kucheriya","year":"2023","unstructured":"Kucheriya, G., Tardos, G.: A characterization of edge-ordered graphs with almost linear extremal functions. Combinatorica 43, 1111\u20131123 (2023)","journal-title":"Combinatorica"},{"key":"187_CR39","doi-asserted-by":"crossref","unstructured":"Kucheriya, G., Tardos, G.: On edge-ordered graphs with linear extremal functions. In Proceedings of the European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMB), pages 688\u2013694 (2023)","DOI":"10.5817\/CZ.MUNI.EUROCOMB23-095"},{"key":"187_CR40","doi-asserted-by":"crossref","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, Ser. A 165, 32\u201343 (2019)","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"4","key":"187_CR41","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF01302967","volume":"14","author":"M Klazar","year":"1994","unstructured":"Klazar, M., Valtr, P.: Generalized Davenport-Schinzel sequences. Combinatorica 14(4), 463\u2013476 (1994)","journal-title":"Combinatorica"},{"issue":"1","key":"187_CR42","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF01758836","volume":"8","author":"JSB Mitchell","year":"1992","unstructured":"Mitchell, J.S.B.: $${L}_1$$ shortest paths among polygonal obstacles in the plane. Algorithmica 8(1), 55\u201388 (1992)","journal-title":"Algorithmica"},{"issue":"1","key":"187_CR43","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.jcta.2004.04.002","volume":"107","author":"A Marcus","year":"2004","unstructured":"Marcus, A., Tardos, G.: Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A 107(1), 153\u2013160 (2004)","journal-title":"J. Combin. Theory Ser. A"},{"issue":"6","key":"187_CR44","first-page":"895","volume":"42","author":"A Methuku","year":"2022","unstructured":"Methuku, A., Tomon, I.: Bipartite Tur\u00e1n problems for ordered graphs. Comb. 42(6), 895\u2013911 (2022)","journal-title":"Comb."},{"issue":"3","key":"187_CR45","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1706591.1706597","volume":"57","author":"G Nivasch","year":"2010","unstructured":"Nivasch, G.: Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations. J. ACM 57(3), 1\u201344 (2010)","journal-title":"J. ACM"},{"key":"187_CR46","unstructured":"Pettie, S.: Splay trees, Davenport-Schinzel sequences, and the deque conjecture. In Proceedings 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1115\u20131124 (2008)"},{"key":"187_CR47","doi-asserted-by":"crossref","unstructured":"Pettie, S.: Applications of forbidden 0\u20131 matrices to search tree- and path compression-based data structures. In Proceedings 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1457\u20131467 (2010)","DOI":"10.1137\/1.9781611973075.118"},{"key":"187_CR48","doi-asserted-by":"crossref","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. Discret. Math. 311, 2396\u20132410 (2011)","journal-title":"Discret. Math."},{"issue":"6","key":"187_CR49","doi-asserted-by":"crossref","first-page":"1863","DOI":"10.1016\/j.jcta.2011.02.011","volume":"118","author":"S Pettie","year":"2011","unstructured":"Pettie, S.: Generalized Davenport-Schinzel sequences and their 0\u20131 matrix counterparts. J. Comb. Theory Ser. A 118(6), 1863\u20131895 (2011)","journal-title":"J. Comb. Theory Ser. A"},{"key":"187_CR50","doi-asserted-by":"crossref","unstructured":"Pettie, S.: On the structure and composition of forbidden sequences, with geometric applications. In Proceedings 27th Annual Symposium on Computational Geometry (SoCG), pages 370\u2013379 (2011)","DOI":"10.1145\/1998196.1998258"},{"issue":"5","key":"187_CR51","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1145\/2794075","volume":"62","author":"S Pettie","year":"2015","unstructured":"Pettie, S.: Sharp bounds on Davenport-Schinzel sequences of every order. J. ACM 62(5), 36 (2015)","journal-title":"J. ACM"},{"issue":"4","key":"187_CR52","doi-asserted-by":"crossref","first-page":"2189","DOI":"10.1137\/140968574","volume":"29","author":"S Pettie","year":"2015","unstructured":"Pettie, S.: Three generalizations of Davenport-Schinzel sequences. SIAM J. Discrete Mathematics 29(4), 2189\u20132238 (2015)","journal-title":"SIAM J. Discrete Mathematics"},{"issue":"3","key":"187_CR53","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1137\/0220029","volume":"20","author":"J Pach","year":"1991","unstructured":"Pach, J., Sharir, M.: On vertical visibility in arrangements of segments and the queue size in the Bentley-Ottmann line sweeping algorithm. SIAM J. Comput. 20(3), 460\u2013470 (1991)","journal-title":"SIAM J. Comput."},{"key":"187_CR54","unstructured":"Park, S.G., Shi, Q.: New bounds on extremal numbers in acyclic ordered graphs. https:\/\/math.mit.edu\/news\/summer\/SPURprojects\/2013ParkShi.pdf, (2013)"},{"key":"187_CR55","doi-asserted-by":"crossref","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. Israel J. Math. 155, 359\u2013380 (2006)","journal-title":"Israel J. Math."},{"key":"187_CR56","doi-asserted-by":"crossref","unstructured":"Pettie, S., Tardos, G.: On the extremal functions of acyclic forbidden 0-1 matrices. In Proceedings 35th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1166\u20131176 (2024)","DOI":"10.1137\/1.9781611977912.45"},{"key":"187_CR57","unstructured":"Sharir, M., Agarwal, P.: Davenport-Schinzel Sequences and their Geometric Applications. Cambridge University Press (1995)"},{"key":"187_CR58","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1007\/s11856-017-1455-5","volume":"217","author":"A Shapira","year":"2017","unstructured":"Shapira, A., Yuster, R.: A tournament approach to pattern avoiding matrices. Israel J. Math. 217, 477\u2013505 (2017)","journal-title":"Israel J. Math."},{"issue":"2","key":"187_CR59","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1016\/j.jcta.2004.11.015","volume":"111","author":"G Tardos","year":"2005","unstructured":"Tardos, G.: On 0\u20131 matrices and small excluded submatrices. J. Combin. Theory Ser. A 111(2), 266\u2013288 (2005)","journal-title":"J. Combin. Theory Ser. A"},{"key":"187_CR60","first-page":"436","volume":"48","author":"P Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n, P.: On an extremal problem in graph theory. Matematikai \u00e9s Fisikai Lapok 48, 436\u2013452 (1941)","journal-title":"Matematikai \u00e9s Fisikai Lapok"},{"issue":"7","key":"187_CR61","doi-asserted-by":"crossref","first-page":"1987","DOI":"10.1016\/j.disc.2018.03.023","volume":"341","author":"J Wellman","year":"2018","unstructured":"Wellman, J., Pettie, S.: Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices. Discret. Math. 341(7), 1987\u20131993 (2018)","journal-title":"Discret. Math."},{"issue":"1","key":"187_CR62","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF02187894","volume":"3","author":"A Wiernik","year":"1988","unstructured":"Wiernik, A., Sharir, M.: Planar realizations of nonlinear Davenport-Schinzel sequences by segments. Discrete Comput. Geom. 3(1), 15\u201347 (1988)","journal-title":"Discrete Comput. Geom."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00187-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00187-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00187-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T13:18:00Z","timestamp":1767014280000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00187-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,7]]},"references-count":62,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["187"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00187-7","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2025,11,7]]},"assertion":[{"value":"6 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 October 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 November 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"59"}}