First-Order Convergence and Roots

Christofides, Demetres and Kral, Daniel (2016) First-Order Convergence and Roots. Combinatorics, Probability and Computing, 25 (02). pp. 213-221. ISSN 0963-5483

[thumbnail of Author Accepted Manuscript]
Preview
PDF (Author Accepted Manuscript) - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

278kB

Official URL: https://doi.org/10.1017/S0963548315000048

Abstract

Nesetril 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\in\mathbb{N}}$ 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\in\mathbb{N}}$ 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.


Repository Staff Only: item control page