Decomposition horizons and a characterization of stable hereditary classes of graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F25%3A00637116" target="_blank" >RIV/67985807:_____/25:00637116 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/25:10511784

Výsledek na webu

<a href="https://doi.org/10.1016/j.ejc.2025.104130" target="_blank" >https://doi.org/10.1016/j.ejc.2025.104130</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejc.2025.104130" target="_blank" >10.1016/j.ejc.2025.104130</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Decomposition horizons and a characterization of stable hereditary classes of graphs

Popis výsledku v původním jazyce

The notions of bounded-size and quasibounded-size decompositions with bounded treedepth base classes are central to the structural theory of graph sparsity introduced by two of the authors years ago, and provide a characterization of both classes with bounded expansions and nowhere dense classes. Strong connections of this theory with model theory led to considering first-order transductions, which are logically defined graph transformations, and to initiate a comparative study of combinatorial and model theoretical properties of graph classes, with an emphasis on the model theoretical notions of dependence (or NIP) and stability. In this paper, we first prove that the model theoretic notions of dependence and stability are, for hereditary classes of graphs, compatible with quasibounded-size decompositions, in the following sense: every hereditary class with quasibounded-size decompositions with dependent (resp. stable) base classes is itself dependent (resp. stable). This result is obtained in a more general study of “decomposition horizons”, which are class properties compatible with quasibounded-size decompositions. We deduce that hereditary classes with quasibounded-size decompositions with bounded shrubdepth base classes are stable. In the second part of the paper, we prove the converse. Thus, we characterize stable hereditary classes of graphs as those hereditary classes that admit quasibounded-size decompositions with bounded shrubdepth base classes. This result is obtained by proving that every hereditary stable class of graphs admits almost nowhere dense quasi-bush representations, thus answering positively a conjecture of Dreier et al. These results have several consequences. For example, we show that every graph G in a stable, hereditary class of graphs C has a clique or a stable set of size ΩC,ɛ(|G|1/2−ɛ), for every ɛ>0, which is tight in the sense that it cannot be improved to ΩC(|G|1/2).

Název v anglickém jazyce

Decomposition horizons and a characterization of stable hereditary classes of graphs

Popis výsledku anglicky

The notions of bounded-size and quasibounded-size decompositions with bounded treedepth base classes are central to the structural theory of graph sparsity introduced by two of the authors years ago, and provide a characterization of both classes with bounded expansions and nowhere dense classes. Strong connections of this theory with model theory led to considering first-order transductions, which are logically defined graph transformations, and to initiate a comparative study of combinatorial and model theoretical properties of graph classes, with an emphasis on the model theoretical notions of dependence (or NIP) and stability. In this paper, we first prove that the model theoretic notions of dependence and stability are, for hereditary classes of graphs, compatible with quasibounded-size decompositions, in the following sense: every hereditary class with quasibounded-size decompositions with dependent (resp. stable) base classes is itself dependent (resp. stable). This result is obtained in a more general study of “decomposition horizons”, which are class properties compatible with quasibounded-size decompositions. We deduce that hereditary classes with quasibounded-size decompositions with bounded shrubdepth base classes are stable. In the second part of the paper, we prove the converse. Thus, we characterize stable hereditary classes of graphs as those hereditary classes that admit quasibounded-size decompositions with bounded shrubdepth base classes. This result is obtained by proving that every hereditary stable class of graphs admits almost nowhere dense quasi-bush representations, thus answering positively a conjecture of Dreier et al. These results have several consequences. For example, we show that every graph G in a stable, hereditary class of graphs C has a clique or a stable set of size ΩC,ɛ(|G|1/2−ɛ), for every ɛ>0, which is tight in the sense that it cannot be improved to ΩC(|G|1/2).

Druh

J_imp - Článek v periodiku v databázi Web of Science

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

European Journal of Combinatorics

ISSN

0195-6698

e-ISSN

1095-9971

Svazek periodika

129

Číslo periodika v rámci svazku

October 2025

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

27

Strana od-do

104130

Kód UT WoS článku

001536475700001

EID výsledku v databázi Scopus

2-s2.0-85217027099