Twin-width and permutations Article Swipe

PDF

Related Concepts

Combinatorics Permutation (music) Mathematics Bounded function Permutation graph Invariant (physics) Pairwise comparison Discrete mathematics Binary number Class (philosophy) Vertex (graph theory) Graph Computer science Arithmetic Physics Artificial intelligence Acoustics Statistics Mathematical physics Mathematical analysis

Édouard Bonnet , Jaroslav Nešetřil , Patrice Ossona de Mendez , Sebastian Siebertz , Stéphan Thomassé ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.46298/lmcs-20(3:4)2024 · OA: W4400428279

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.

Twin-width and permutations Article Swipe

Related Topics