É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.

    https://doi.org/10.46298/lmcs-20(3:4)2024
    Source: arXiv.org:2102.06880
    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
    Licence: Attribution 4.0 International (CC BY 4.0)
    Funding:
      Source : OpenAIRE Graph
    • Dynamics and Structure of Networks; Funder: European Commission; Code: 810115

    Classifications

    Mathematics Subject Classification 20201
    Sources:
    • [1] zbMATH Open.

    Share and export

    Consultation statistics

    This page has been seen 1298 times.
    This article's PDF has been downloaded 497 times.