Strong Modeling Limits of Graphs with Bounded Tree-Width

GRZESIK, Andrzej, Daniel KRÁĽ a Josef Samuel MOHR. Strong Modeling Limits of Graphs with Bounded Tree-Width. In Trends in Mathematics, Volume 14, Extended Abstracts of EuroComb 2021, European Conference on Combinatorics, Graph Theory and Applications. Barcelona: Birkhäuser, 2021, s. 273-279. ISBN 978-3-030-83822-5. Dostupné z: https://dx.doi.org/10.1007/978-3-030-83823-2_43.

Základní údaje

Originální název

Strong Modeling Limits of Graphs with Bounded Tree-Width

Autoři

GRZESIK, Andrzej (616 Polsko), Daniel KRÁĽ (203 Česká republika, domácí) a Josef Samuel MOHR (276 Německo, domácí)

Vydání

Barcelona, Trends in Mathematics, Volume 14, Extended Abstracts of EuroComb 2021, European Conference on Combinatorics, Graph Theory and Applications, od s. 273-279, 7 s. 2021

Nakladatel

Birkhäuser

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Švýcarsko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Kód RIV

RIV/00216224:14330/21:00126000

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-83822-5

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-83823-2_43

Klíčová slova anglicky

combinatorial limit; first order convergence; graph limit; modeling limit

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

The notion of first order convergence of graphs unifies the notions of convergence for sparse and dense graphs. Nešetřil and Ossona de Mendez [J. Symbolic Logic 84 (2019), 452–472] proved that every first order convergent sequence of graphs from a nowhere-dense class of graphs has a modeling limit and conjectured the existence of such modeling limits with an additional property, the strong finitary mass transport principle. The existence of modeling limits satisfying the strong finitary mass transport principle was proved for first order convergent sequences of trees by Nešetřil and Ossona de Mendez [Electron. J. Combin. 23 (2016), P2.52] and for first order sequences of graphs with bounded path-width by Gajarský et al. [Random Structures Algorithms 50 (2017), 612–635]. We establish the existence of modeling limits satisfying the strong finitary mass transport principle for first order convergent sequences of graphs with bounded tree-width.