On First-Order Transductions of Classes of Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F25%3A00639366" target="_blank" >RIV/67985807:_____/25:00639366 - isvavai.cz</a>
Alternative codes found
RIV/00216208:11320/25:10511781
Result on the web
<a href="https://doi.org/10.46298/lmcs-21(2:26)2025" target="_blank" >https://doi.org/10.46298/lmcs-21(2:26)2025</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.46298/lmcs-21(2:26)2025" target="_blank" >10.46298/lmcs-21(2:26)2025</a>
Alternative languages
Result language
angličtina
Original language name
On First-Order Transductions of Classes of Graphs
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>SC</sub> - Article in a specialist periodical, which is included in the SCOPUS database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/GA21-10775S" target="_blank" >GA21-10775S: Ramsey theory in the context of group theory, model theory and topological dynamics</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Logical Methods in Computer Science
ISSN
1860-5974
e-ISSN
1860-5974
Volume of the periodical
21
Issue of the periodical within the volume
2
Country of publishing house
DE - GERMANY
Number of pages
59
Pages from-to
26
UT code for WoS article
—
EID of the result in the Scopus database
2-s2.0-105009421471