On First-Order Transductions of Classes of Graphs

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/00216208:11320/25:10511781

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

On First-Order Transductions of Classes of Graphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On First-Order Transductions of Classes of Graphs

Popis výsledku anglicky

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.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA21-10775S" target="_blank" >GA21-10775S: Ramseyova teorie v kontextu teorie grup, teorie modelů a topologické dynamiky</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Logical Methods in Computer Science

ISSN

1860-5974

e-ISSN

1860-5974

Svazek periodika

21

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

59

Strana od-do

26

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-105009421471