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

DOI10.1002/RSA.20676MaRDI QIDQ4978432zbMATH OpenOpenAlexFDO

Authors Jakub Gajarský, Petr Hliněný, Tomáš Kaiser, Martin Kupec, Jan Obdržálek, Sebastian Ordyniak, Vojtěch Tůma, Daniel Král'

Publication date 10 August 2017

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.08122, http://wrap.warwick.ac.uk/78596/9/WRAP-first-order-limits-sparse-graphs-Kral-2017.pdf

zbMATH Keywords

graph limitsfirst order logicfirst order limitsgraphs with bounded path-width

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Density (toughness, etc.) (05C42)

Abstract: Nesetril 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.

Recommendations

• First-Order Convergence and Roots
• Existence of modeling limits for sequences of sparse structures
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• First order convergence of matroids
• Limits of random trees. II

Cites work

• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Convergent sequences of sparse graphs: a large deviations approach
• Graph theory
• Limits of dense graph sequences
• Limits of locally-globally convergent graph sequences
• On limits of finite graphs
• Processes on unimodular random networks
• Sparse graphs: metrics and random models
• Sparsity. Graphs, structures, and algorithms
• Testing properties of graphs and functions

Cited in

(6)

• Local-global convergence, an analytic and structural approach
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• Modeling limits in hereditary classes: reduction and application to trees
• Approximations of mappings
• Limits of structures and the example of tree semi-lattices
• Existence of modeling limits for sequences of sparse structures

This page was built for publication: First order limits of sparse graphs: plane trees and path-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978432)