一句话：系统研究图类的一阶转导拟序，证明局部范式，并揭示其非格性、路径宽度层级严格性及弱稀疏类作用。
本文研究图类上的一阶（FO）转导拟序，它通过一阶公式能否将一类图编码到另一类来衡量图类的相对复杂度。与一元二阶逻辑转导拟序被猜测较为简单不同，FO 转导拟序非常复杂，结构图论与模型论中的许多标准性质会自然出现。作者证明了一般性结果与构造，其中核心是转导之间的局部范式，并用若干例子及对简单图类转导的刻画加以说明。随后分析该拟序的多个方面：某些性质最小/最大类的存在与否、路径宽度层级的严格性、该拟序不构成格，以及弱稀疏类在其间的作用。
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.
@article{paperbot3405,
title = {On first-order transductions of classes of graphs},
author = {Samuel Braunfeld and Jaroslav Nešetřil and Patrice Ossona de Mendez and Sebastian Siebertz},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 2},
year = {2025},
doi = {10.46298/lmcs-21(2:26)2025}
}