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

DOI10.1002/RSA.20676zbMATH Open1368.05088arXiv1504.08122OpenAlexW1759318922MaRDI QIDQ4978432FDOQ4978432

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)

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.

Full work available at URL: https://arxiv.org/abs/1504.08122

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

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)

Cites Work

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

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)