×

First order limits of sparse graphs: plane trees and path-width. (English) Zbl 1368.05088

Summary: J. Nešetřil and P. Ossona de Mendez [Commentat. Math. Univ. Carol. 53, No. 4, 581–603 (2012; Zbl 1274.05464); “A unified approach to structural limits, and limits of graphs with bounded tree-depth”, Preprint, arXiv:1303.6471] 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.

MSC:

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

Citations:

Zbl 1274.05464
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Aldous, Processes on unimodular random networks, Electron J Probab 12 pp 1454– (2007) · Zbl 1131.60003 · doi:10.1214/EJP.v12-463
[2] Benjamni, Recurrence of distributional limits of finite planar graphs, Electron J Probab 6 pp 1– (2001)
[3] Bollobás, Sparse graphs: Metrics and random models, Random Struct Algorithms 39 pp 1– (2011) · Zbl 1223.05271 · doi:10.1002/rsa.20334
[4] C. Borgs J. T. Chayes D. Gamarnik Convergent sequences of sparse graphs: A large deviations approach · Zbl 1370.05119
[5] Borgs, Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing, Adv Math Vol. 219 pp 1801– (2008) · Zbl 1213.05161 · doi:10.1016/j.aim.2008.07.008
[6] Borgs, Convergent sequences of dense graphs II. Multiway cuts and statistical physics, Ann Math 176 pp 151– (2012) · Zbl 1247.05124 · doi:10.4007/annals.2012.176.1.2
[7] Borgs, Proceedings of 38rd Annual ACM Symposium on the Theory of Computing (STOC) pp 261– (2006)
[8] Diestel, Graph theory (2010) · Zbl 1204.05001 · doi:10.1007/978-3-642-14279-6
[9] Ebbinghaus, Finite model theory (2005)
[10] Elek, Note on limits of finite graphs, Combinatorica 27 pp 503– (2007) · Zbl 1164.05061 · doi:10.1007/s00493-007-2214-8
[11] Hatami, Limits of local-global convergent graph sequences, Geom Funct Anal 24 pp 269– (2014) · Zbl 1294.05109 · doi:10.1007/s00039-014-0258-7
[12] F. Kardoš D. Král’ A. Liebenau L. Mach First order convergence of matroids
[13] Lovász, Large networks and graph limits (2012) · doi:10.1090/coll/060
[14] Lovász, Limits of dense graph sequences, J Combin Theory Ser B 96 pp 933– (2006) · Zbl 1113.05092 · doi:10.1016/j.jctb.2006.05.002
[15] Lovász, Testing properties of graphs and functions, Israel J Math 178 pp 113– (2010) · Zbl 1246.05106 · doi:10.1007/s11856-010-0060-7
[16] Nešetřil, A model theory approach to structural limits, Comment Math Univ Carolin 53 pp 581– (2012)
[17] J. Nešetřil P. Ossona de Mendez A unified approach to structural limits, and limits of graphs with bounded tree-depth
[18] J. Nešetřil P. Ossona de Mendez Modeling limits in hereditary classes: Reduction and application to trees
[19] Nešetřil, Sparsity: Graphs, structures, and algorithms (2012) · Zbl 1268.05002 · doi:10.1007/978-3-642-27875-4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.