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.

Basic information

Original name

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

Authors

GAJARSKÝ, Jakub (703 Slovakia, belonging to the institution); Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution); Tomáš KAISER (203 Czech Republic); Daniel KRÁĽ (203 Czech Republic); Martin KUPEC (203 Czech Republic); Jan OBDRŽÁLEK (203 Czech Republic, belonging to the institution); Sebastian ORDYNIAK (276 Germany, belonging to the institution) and Vojtěch TŮMA (203 Czech Republic)

Edition

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

Other information

Language

English

Type of outcome

Article in a journal

Field of Study

10101 Pure mathematics

Country of publisher

United States of America

Confidentiality degree

is not subject to a state or trade secret

Impact factor

Impact factor: 0.985

RIV identification code

RIV/00216224:14330/17:00094633

Organization unit

Faculty of Informatics

DOI

https://doi.org/10.1002/rsa.20676

UT WoS

000405296900004

EID Scopus

2-s2.0-84986205748

Keywords in English

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

Abstract

In the original language

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.

Links

GA14-03501S, research and development project

Name: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky

Investor: Czech Science Foundation

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

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

Investor: Masaryk University, Category A

Cite

GAJARSKÝ, Jakub; Petr HLINĚNÝ; Tomáš KAISER; Daniel KRÁĽ; Martin KUPEC; Jan OBDRŽÁLEK; Sebastian ORDYNIAK and Vojtěch TŮMA. First order limits of sparse graphs: Plane trees and path-width. Random Structures & Algorithms. Wiley, 2017, vol. 50, No 4, p. 612-635. ISSN 1042-9832. Available from: https://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 = {https://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 and Vojtěch TŮMA. First order limits of sparse graphs: Plane trees and path-width. \textit{Random Structures \&{} Algorithms}. Wiley, 2017, vol.~50, No~4, p.~612-635. ISSN~1042-9832. Available from: https://doi.org/10.1002/rsa.20676.

Přehled o publikaci