{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:49:14Z","timestamp":1770994154422,"version":"3.50.1"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Inspired by a width invariant on permutations defined by Guillemot and Marx,\nBonnet, Kim, Thomass\\'e, and Watrigant introduced the twin-width of graphs,\nwhich is a parameter describing its structural complexity. This invariant has\nbeen further extended to binary structures, in several (basically equivalent)\nways. We prove that a class of binary relational structures (that is:\nedge-colored partially directed graphs) has bounded twin-width if and only if\nit is a first-order transduction of a~proper permutation class. As a\nby-product, we show that every class with bounded twin-width contains at most\n$2^{O(n)}$ pairwise non-isomorphic $n$-vertex graphs.<\/jats:p>","DOI":"10.46298\/lmcs-20(3:4)2024","type":"journal-article","created":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T06:40:06Z","timestamp":1720420806000},"source":"Crossref","is-referenced-by-count":3,"title":["Twin-width and permutations"],"prefix":"10.46298","volume":"Volume 20, Issue 3","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[]},{"given":"Jaroslav","family":"Ne\u0161et\u0159il","sequence":"additional","affiliation":[]},{"given":"Patrice Ossona","family":"de Mendez","sequence":"additional","affiliation":[]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2024,7,8]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/13880\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/13880\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T06:40:07Z","timestamp":1720420807000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/11112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-20(3:4)2024","relation":{"has-preprint":[{"id-type":"arxiv","id":"2102.06880v5","asserted-by":"subject"},{"id-type":"arxiv","id":"2102.06880v3","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2102.06880","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2102.06880","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,8]]},"article-number":"11112"}}