Modeling limits in hereditary classes: Reduction and application to trees

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10333127" target="_blank" >RIV/00216208:11320/16:10333127 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p52" target="_blank" >http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p52</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Modeling limits in hereditary classes: Reduction and application to trees

Popis výsledku v původním jazyce

The study of limits of graphs led to elegant limit structures for sparse and dense graphs. This has been unified and generalized by the authors in a more general setting combining analytic tools and model theory to FO-limits (and X-limits) and to the notion of modeling. The existence of modeling limits was established for sequences in a bounded degree class and, in addition, to the case of classes of trees with bounded height and of graphs with bounded tree depth. The natural obstacle for the existence of modeling limit for a monotone class of graphs is the nowhere dense property and it has been conjectured that this is a sufficient condition. Extending earlier results here we derive several general results which present a realistic approach to this conjecture. As an example we then prove that the class of all finite trees admits modeling limits.

Název v anglickém jazyce

Modeling limits in hereditary classes: Reduction and application to trees

Popis výsledku anglicky

The study of limits of graphs led to elegant limit structures for sparse and dense graphs. This has been unified and generalized by the authors in a more general setting combining analytic tools and model theory to FO-limits (and X-limits) and to the notion of modeling. The existence of modeling limits was established for sequences in a bounded degree class and, in addition, to the case of classes of trees with bounded height and of graphs with bounded tree depth. The natural obstacle for the existence of modeling limit for a monotone class of graphs is the nowhere dense property and it has been conjectured that this is a sufficient condition. Extending earlier results here we derive several general results which present a realistic approach to this conjecture. As an example we then prove that the class of all finite trees admits modeling limits.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

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

Electronic Journal of Combinatorics

ISSN

1077-8926

e-ISSN

—

Svazek periodika

23

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

33

Strana od-do

1-33

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-84976262150