Édouard Bonnet ; Jaroslav Nešetřil ; Patrice Ossona de Mendez ; Sebastian Siebertz ; Stéphan Thomassé - Twin-width and permutations

lmcs:11112 - Logical Methods in Computer Science, July 8, 2024, Volume 20, Issue 3 - https://doi.org/10.46298/lmcs-20(3:4)2024
Twin-width and permutationsArticle

Authors: Édouard Bonnet ; Jaroslav Nešetřil ; Patrice Ossona de Mendez ; Sebastian Siebertz ; Stéphan Thomassé

    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.


    Volume: Volume 20, Issue 3
    Published on: July 8, 2024
    Accepted on: March 31, 2024
    Submitted on: March 24, 2023
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Discrete Mathematics,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 881 times.
    This article's PDF has been downloaded 437 times.