Hostname: page-component-7c8c6479df-nwzlb Total loading time: 0 Render date: 2024-03-29T07:52:39.426Z Has data issue: false hasContentIssue false

First-Order Convergence and Roots

Published online by Cambridge University Press:  24 February 2015

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)

Abstract

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 (Gi)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 (vi)i∈ℕ of vertices such that the graphs Gi rooted at vi 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.

Type
Paper
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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 14541508.Google Scholar
[2] Benjamini, I. and Schramm, O. (2001) Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 113.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. 261270.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 18011851.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 151219.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 503507.Google Scholar
[9] Hatami, H., Lovász, L. and Szegedy, B. Limits of locally-globally convergent graph sequences. Geom. Funct. Anal., 24 (2014), 269296.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 933957.Google Scholar
[13] Lovász, L. and Szegedy, B. (2010) Testing properties of graphs and functions. Israel J. Math. 178 113156.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), 581603.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