Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-08T14:46:09.009Z Has data issue: false hasContentIssue false
  • English
  • Français

First-Order Convergence and Roots†

Part of: Graph theory Miscellaneous topics in measure theory Model theory

Published online by Cambridge University Press:  24 February 2015

DEMETRES CHRISTOFIDES  and
DANIEL KRÁL’
DEMETRES CHRISTOFIDES
Affiliation:
School of Sciences, UCLan Cyprus, 12–14 University Avenue, 7080 Pyla, Cyprus (e-mail: dchristofides@uclan.ac.uk)
DANIEL KRÁL’
Affiliation:
Mathematics Institute, DIMAP and Department of Computer Science, University of Warwick, Coventry CV4 7AL, UK (e-mail: d.kral@warwick.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Nešetřil and Ossona de Mendez introduced the notion of first-order convergence, which unifies the notions of convergence for sparse and dense graphs. They asked whether, if (G i )i∈ℕ is a sequence of graphs with M being their first-order limit and v is a vertex of M, then there exists a sequence (v i )i∈ℕ of vertices such that the graphs G i rooted at v i converge to M rooted at v. We show that this holds for almost all vertices v of M, and we give an example showing that the statement need not hold for all vertices.

MSC classification

Primary: 03C98: Applications of model theory
Secondary: 05C63: Infinite graphs 28E15: Other connections with logic and set theory

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 2 , March 2016 , pp. 213 - 221
Copyright
Copyright © Cambridge University Press 2015 

Footnotes

†

This work was done during a visit to the Institut Mittag-Leffler (Djursholm, Sweden).

References

[1] Aldous, D. and Lyons, R. (2007) Processes on unimodular random networks. Electron. J. Probab. 12 1454–1508.Google Scholar
[2] Benjamini, I. and Schramm, O. (2001) Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 1–13.Google Scholar
[3] Borgs, C., Chayes, J., Lovász, L., Sós, V. T., Szegedy, B. and Vesztergombi, K. (2006) Graph limits and parameter testing. In Proc. 38rd Annual ACM Symposium on the Theory of Computing: STOC, ACM, pp. 261–270.Google Scholar
[4] Borgs, C., Chayes, J. T., Lovász, L., Sós, V. T. and Vesztergombi, K. (2008) Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Adv. Math. 219 1801–1851.Google Scholar
[5] Borgs, C., Chayes, J. T., Lovász, L., Sós, V. T. and Vesztergombi, K. (2012) Convergent sequences of dense graphs II: Multiway cuts and statistical physics. Ann. of Math. 176 151–219.Google Scholar
[6] Diestel, R. (2010) Graph Theory, Springer.Google Scholar
[7] Ebbinghaus, H.-D. and Flum, J. (2005) Finite Model Theory, Springer.Google Scholar
[8] Elek, G. (2007) Note on limits of finite graphs. Combinatorica 27 503–507.Google Scholar
[9] Hatami, H., Lovász, L. and Szegedy, B. Limits of locally-globally convergent graph sequences. Geom. Funct. Anal., 24 (2014), 269–296.Google Scholar
[10] Král', D., Kupec, M. and Tůma, V. Modelings of trees. In preparation.Google Scholar
[11] Lovász, L. (2012) Large Networks and Graph Limits, AMS.CrossRefGoogle Scholar
[12] Lovász, L. and Szegedy, B. (2006) Limits of dense graph sequences. J. Combin. Theory Ser. B 96 933–957.Google Scholar
[13] Lovász, L. and Szegedy, B. (2010) Testing properties of graphs and functions. Israel J. Math. 178 113–156.Google Scholar
[14] Nešetřil, J. and Ossona de Mendez, P. A model theory approach to structural limits, Comment. Math. Univ. Carolin. 53 (2012), 581–603.Google Scholar
[15] Nešetřil, J. and Ossona de Mendez, P. A unified approach to structural limits, and limits of graphs with bounded tree-depth. arXiv:1303.6471 Google Scholar
[16] Nešetřil, J. and Ossona de Mendez, P. Modeling limits in hereditary classes: Reduction and application to trees. arXiv:1312.0441 Google Scholar