一句话：证明二元关系结构类具有有界 Twin-width 当且仅当它是某个真排列类的一阶转换。
Twin-width 是 Bonnet 等人受 Guillemot 与 Marx 定义的排列宽度不变量启发而提出的图结构复杂度参数，并可扩展到二元结构。本文研究哪些二元关系结构类（边着色且部分定向的图）具有有界 Twin-width。作者证明，一个二元关系结构类具有有界 Twin-width，当且仅当它可以由某个真排列类经一阶转换（first-order transduction）得到。该刻画把 Twin-width 的有界性与排列类的模型论可定义性联系起来。作为副产品，文章还证明每个有界 Twin-width 类至多包含 2^{O(n)} 个两两不同构的 n 顶点图，给出了此类结构类的计数上界。
Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomass\'e, and Watrigant introduced the twin-width of graphs, which is a parameter describing its structural complexity. This invariant has been further extended to binary structures, in several (basically equivalent) ways. We prove that a class of binary relational structures (that is: edge-colored partially directed graphs) has bounded twin-width if and only if it is a first-order transduction of a~proper permutation class. As a by-product, we show that every class with bounded twin-width contains at most $2^{O(n)}$ pairwise non-isomorphic $n$-vertex graphs.
@article{paperbot2745,
title = {Twin-width and permutations},
author = {Édouard Bonnet and Jaroslav Nešetřil and Patrice Ossona de Mendez and Sebastian Siebertz and Stéphan Thomassé},
journal = {Logical Methods in Computer Science},
volume = {Volume 20, Issue 3},
year = {2024},
doi = {10.46298/lmcs-20(3:4)2024}
}