{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T22:04:56Z","timestamp":1773093896104,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T00:00:00Z","timestamp":1718236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council"},{"name":"European Union\u2019s Horizon 2020","award":["810115, and 948057"],"award-info":[{"award-number":["810115, and 948057"]}]},{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","award":["ANR-21-CE48-0014-01, and ANR-19-CE48-0013-01"],"award-info":[{"award-number":["ANR-21-CE48-0014-01, and ANR-19-CE48-0013-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory.<\/jats:p>\n          <jats:p>\n            This has several consequences. First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh et\u00a0al.\u00a0[\n            <jats:xref ref-type=\"bibr\">5<\/jats:xref>\n            ] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture\/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width. Finally, it settles the small conjecture\u00a0[\n            <jats:xref ref-type=\"bibr\">8<\/jats:xref>\n            ] in the case of ordered graphs.\n          <\/jats:p>","DOI":"10.1145\/3651151","type":"journal-article","created":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T12:13:40Z","timestamp":1710159220000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Twin-Width IV: Ordered Graphs and Matrices"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1653-5822","authenticated-orcid":false,"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[{"name":"ENS de Lyon, LIP UMR5668, Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0682-0654","authenticated-orcid":false,"given":"Ugo","family":"Giocanti","sequence":"additional","affiliation":[{"name":"Univ. Grenoble Alpes, CNRS, Laboratoire G-SCOP, Grenoble, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0724-3729","authenticated-orcid":false,"given":"Patrice Ossona","family":"de Mendez","sequence":"additional","affiliation":[{"name":"CAMS CNRS UMR 8557, Paris, France and Charles University, Prague, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2923-8202","authenticated-orcid":false,"given":"Pierre","family":"Simon","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7090-1790","authenticated-orcid":false,"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[{"name":"ENS de Lyon, LIP UMR5668, Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1130-9033","authenticated-orcid":false,"given":"Szymon","family":"Toru\u0144czyk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warszawa Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,13]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.06.048"},{"key":"e_1_3_4_3_2","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/3-540-19488-6_105","volume-title":"Automata, Languages and Programming","author":"Arnborg Stefan","year":"1988","unstructured":"Stefan Arnborg, Jens Lagergren, and Detlef Seese. 1988. Problems easy for tree-decomposable graphs (extended abstract). In Automata, Languages and Programming, Timo Lepist\u00f6 and Arto Salomaa (Eds.). Springer Berlin, Berlin, 38\u201351."},{"issue":"3","key":"e_1_3_4_4_2","first-page":"229","article-title":"Second-order quantifiers and the complexity of theories.","volume":"26","author":"Baldwin John T.","year":"1985","unstructured":"John T. Baldwin and Saharon Shelah. 1985. Second-order quantifiers and the complexity of theories. Notre Dame Journal of Formal Logic 26, 3 (1985), 229\u2013303.","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"e_1_3_4_5_2","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/3-540-33700-8_12","volume-title":"Topics in Discrete Mathematics","author":"Balogh J\u00f3zsef","year":"2006","unstructured":"J\u00f3zsef Balogh, B\u00e9la Bollob\u00e1s, and Robert Morris. 2006. Hereditary properties of ordered graphs. In Topics in Discrete Mathematics. Springer, 179\u2013213."},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.05.004"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316106853.002"},{"key":"e_1_3_4_8_2","article-title":"Twin-width III: Max independent set and coloring","volume":"2007","author":"Bonnet \u00c9douard","year":"2020","unstructured":"\u00c9douard Bonnet, Colin Geniet, Eun Jung Kim, St\u00e9phan Thomass\u00e9, and R\u00e9mi Watrigant. 2020. Twin-width III: Max independent set and coloring. CoRR abs\/2007.14161 (2020). arxiv:2007.14161https:\/\/arxiv.org\/abs\/2007.14161","journal-title":"CoRR"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.118"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00062"},{"key":"e_1_3_4_11_2","volume-title":"24th EACSL Annual Conference on Computer Science Logic (CSL\u201915)","author":"Bova Simone","year":"2015","unstructured":"Simone Bova and Barnaby Martin. 2015. First-order queries on finite Abelian groups. In 24th EACSL Annual Conference on Computer Science Logic (CSL\u201915). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_4_12_2","article-title":"F\u00fcredi-Hajnal limits are typically subexponential","volume":"1607","author":"Cibulka Josef","year":"2016","unstructured":"Josef Cibulka and Jan Kyncl. 2016. F\u00fcredi-Hajnal limits are typically subexponential. CoRR abs\/1607.07491 (2016). arxiv:1607.07491http:\/\/arxiv.org\/abs\/1607.07491","journal-title":"CoRR"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90268-2"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.04.003"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.31"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.0026"},{"key":"e_1_3_4_19_2","first-page":"194","volume-title":"1st Conference of the Centre for Discrete Mathematics and Theoretical Computer Science (DMTCS 1996)","author":"Downey Rodney G.","year":"1996","unstructured":"Rodney G. Downey, Michael R. Fellows, and Udayan Taylor. 1996. The parameterized complexity of relational database queries and an improved characterization of W[1]. In 1st Conference of the Centre for Discrete Mathematics and Theoretical Computer Science (DMTCS 1996)). Springer-Verlag, Singapore, 194\u2013213."},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2499483"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/1121738"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504798"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.63"},{"key":"e_1_3_4_24_2","article-title":"A new perspective on FO model checking of dense graph classes","volume":"1805","author":"Gajarsk\u00fd Jakub","year":"2018","unstructured":"Jakub Gajarsk\u00fd, Petr Hlinen\u00fd, Daniel Lokshtanov, Jan Obdrz\u00e1lek, and M. S. Ramanujan. 2018. A new perspective on FO model checking of dense graph classes. CoRR abs\/1805.01823 (2018). arxiv:1805.01823http:\/\/arxiv.org\/abs\/1805.01823","journal-title":"CoRR"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2935314"},{"key":"e_1_3_4_26_2","volume-title":"43rd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201918)","author":"Gajarsk\u00fd Jakub","year":"2018","unstructured":"Jakub Gajarsk\u00fd and Daniel Kr\u00e1\u013e. 2018. Recovering sparse graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201918). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.126"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2003.10.004"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3051095"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2019.07.003"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2018.10.001"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04166-6_22"},{"issue":"1","key":"e_1_3_4_34_2","article-title":"On growth rates of permutations, set partitions, ordered graphs and other objects","volume":"15","author":"Klazar Martin","year":"2008","unstructured":"Martin Klazar. 2008. On growth rates of permutations, set partitions, ordered graphs and other objects. Electron. J. Comb. 15, 1 (2008). http:\/\/www.combinatorics.org\/Volume_15\/Abstracts\/v15i1r75.html","journal-title":"Electron. J. Comb."},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-8(1:27)2012"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.39"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.04.002"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.01.006"},{"key":"e_1_3_4_39_2","volume-title":"Proc. London Math. Soc. series 2 (264-286)","author":"Ramsey Frank P.","year":"1930","unstructured":"Frank P. Ramsey. 1930. On a problem of formal logic. In Proc. London Math. Soc. series 2 (264-286), Vol. 30."},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90054-P"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(05)80203-8"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500070079"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(71)90015-5"},{"key":"e_1_3_4_44_2","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0098503","volume-title":"Monadic Logic: Hanf Numbers. In: Around Classification Theory of Models","author":"Shelah Saharon","year":"1986","unstructured":"Saharon Shelah. 1986. Monadic Logic: Hanf Numbers. In: Around Classification Theory of Models. Lecture Notes in Mathematics, Vol. 1182. Springer, Berlin."},{"key":"e_1_3_4_45_2","unstructured":"Pierre Simon. 2021. A Note on Stability and NIP in One Variable. (2021). arxiv:math.LO\/2103.15799"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651151","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:49:53Z","timestamp":1750286993000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,13]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3651151"],"URL":"https:\/\/doi.org\/10.1145\/3651151","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,13]]},"assertion":[{"value":"2022-05-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}