First order limits of sparse graphs: Plane trees and path-width

J 2017

First order limits of sparse graphs: Plane trees and path-width

GAJARSKÝ, Jakub, Petr HLINĚNÝ, Tomáš KAISER, Daniel KRÁĽ, Martin KUPEC et. al.

Základní údaje

Originální název

First order limits of sparse graphs: Plane trees and path-width

Autoři

GAJARSKÝ, Jakub (703 Slovensko, domácí), Petr HLINĚNÝ (203 Česká republika, garant, domácí), Tomáš KAISER (203 Česká republika), Daniel KRÁĽ (203 Česká republika), Martin KUPEC (203 Česká republika), Jan OBDRŽÁLEK (203 Česká republika, domácí), Sebastian ORDYNIAK (276 Německo, domácí) a Vojtěch TŮMA (203 Česká republika)

Vydání

Random Structures & Algorithms, Wiley, 2017, 1042-9832

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Spojené státy

Utajení

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

Impakt faktor

Impact factor: 0.985

Kód RIV

RIV/00216224:14330/17:00094633

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.1002/rsa.20676

UT WoS

000405296900004

Klíčová slova anglicky

graph limits; graphs with bounded path-width; first order limits

Štítky

formela-journal

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 17. 4. 2018 09:36, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

Nešetřil and Ossona de Mendez introduced the notion of first order convergence as an attempt to unify the notions of convergence for sparse and dense graphs. It is known that there exist first order convergent sequences of graphs with no limit modeling (an analytic representation of the limit). On the positive side, every first order convergent sequence of trees or graphs with no long path (graphs with bounded tree-depth) has a limit modeling. We strengthen these results by showing that every first order convergent sequence of plane trees (trees with embeddings in the plane) and every first order convergent sequence of graphs with bounded path-width has a limit modeling.

Návaznosti

GA14-03501S, projekt VaV

Název: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky

Investor: Grantová agentura ČR, Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky

MUNI/A/0945/2015, interní kód MU

Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace V.

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace V., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

Citovat

GAJARSKÝ, Jakub, Petr HLINĚNÝ, Tomáš KAISER, Daniel KRÁĽ, Martin KUPEC, Jan OBDRŽÁLEK, Sebastian ORDYNIAK a Vojtěch TŮMA. First order limits of sparse graphs: Plane trees and path-width. Random Structures & Algorithms. Wiley, 2017, roč. 50, č. 4, s. 612-635. ISSN 1042-9832. Dostupné z: https://dx.doi.org/10.1002/rsa.20676.

@article{1372353,
   author = {Gajarský, Jakub and Hliněný, Petr and Kaiser, Tomáš and Kráľ, Daniel and Kupec, Martin and Obdržálek, Jan and Ordyniak, Sebastian and Tůma, Vojtěch},
   article_number = {4},
   doi = {http://dx.doi.org/10.1002/rsa.20676},
   keywords = {graph limits; graphs with bounded path-width; first order limits},
   language = {eng},
   issn = {1042-9832},
   journal = {Random Structures & Algorithms},
   title = {First order limits of sparse graphs: Plane trees and path-width},
   volume = {50},
   year = {2017}
}

TY  - JOUR
ID  - 1372353
AU  - Gajarský, Jakub - Hliněný, Petr - Kaiser, Tomáš - Kráľ, Daniel - Kupec, Martin - Obdržálek, Jan - Ordyniak, Sebastian - Tůma, Vojtěch
PY  - 2017
TI  - First order limits of sparse graphs: Plane trees and path-width
JF  - Random Structures & Algorithms
VL  - 50
IS  - 4
SP  - 612-635
EP  - 612-635
PB  - Wiley
SN  - 10429832
KW  - graph limits
KW  - graphs with bounded path-width
KW  - first order limits
N2  - Nešetřil and Ossona de Mendez introduced the notion of first order convergence as an attempt to unify the notions of convergence for sparse and dense graphs. It is known that there exist first order convergent sequences of graphs with no limit modeling (an analytic representation of the limit). On the positive side, every first order convergent sequence of trees or graphs with no long path (graphs with bounded tree-depth) has a limit modeling. We strengthen these results by showing that every first order convergent sequence of plane trees (trees with embeddings in the plane) and every first order convergent sequence of graphs with bounded path-width has a limit modeling.
ER  -

GAJARSKÝ, Jakub, Petr HLINĚNÝ, Tomáš KAISER, Daniel KRÁĽ, Martin KUPEC, Jan OBDRŽÁLEK, Sebastian ORDYNIAK a Vojtěch TŮMA. First order limits of sparse graphs: Plane trees and path-width. \textit{Random Structures \&{} Algorithms}. Wiley, 2017, roč.~50, č.~4, s.~612-635. ISSN~1042-9832. Dostupné z: https://dx.doi.org/10.1002/rsa.20676.

Podrobný výpis o publikaci