Samuel Braunfeld ; Jaroslav Nešetřil ; Patrice Ossona de Mendez ; Sebastian Siebertz - On first-order transductions of classes of graphs

lmcs:9981 - Logical Methods in Computer Science, June 23, 2025, Volume 21, Issue 2 - https://doi.org/10.46298/lmcs-21(2:26)2025
On first-order transductions of classes of graphsArticle

Authors: Samuel Braunfeld ; Jaroslav Nešetřil ; Patrice Ossona de Mendez ; Sebastian Siebertz

    We study various aspects of the first-order transduction quasi-order on graph classes, which provides a way of measuring the relative complexity of graph classes based on whether one can encode the other using a formula of first-order (FO) logic. In contrast with the conjectured simplicity of the transduction quasi-order for monadic second-order logic, the FO-transduction quasi-order is very complex, and many standard properties from structural graph theory and model theory naturally appear in it. We prove a local normal form for transductions among other general results and constructions, which we illustrate via several examples and via the characterizations of the transductions of some simple classes. We then turn to various aspects of the quasi-order, including the (non-)existence of minimum and maximum classes for certain properties, the strictness of the pathwidth hierarchy, the fact that the quasi-order is not a lattice, and the role of weakly sparse classes in the quasi-order.


    Volume: Volume 21, Issue 2
    Published on: June 23, 2025
    Accepted on: March 12, 2025
    Submitted on: August 31, 2022
    Keywords: Combinatorics,Discrete Mathematics,Logic in Computer Science,Logic

    Consultation statistics

    This page has been seen 181 times.
    This article's PDF has been downloaded 52 times.