Twin-width and permutations
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911977770582016 |
|---|---|
| author | Bonnet, Édouard Nešetřil, Jaroslav de Mendez, Patrice Ossona Siebertz, Sebastian Thomassé, Stéphan |
| author_facet | Bonnet, Édouard Nešetřil, Jaroslav de Mendez, Patrice Ossona Siebertz, Sebastian Thomassé, Stéphan |
| contents | Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomassé, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2102_06880 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Twin-width and permutations Bonnet, Édouard Nešetřil, Jaroslav de Mendez, Patrice Ossona Siebertz, Sebastian Thomassé, Stéphan Logic in Computer Science Discrete Mathematics Combinatorics Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomassé, 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. |
| title | Twin-width and permutations |
| topic | Logic in Computer Science Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2102.06880 |