First-Order Convergence and Roots†. (24th February 2015)

• Record Type: Journal Article
• Authors: CHRISTOFIDES, DEMETRES; KRÁL', DANIEL
• Is Part Of: Combinatorics, probability and computing. Volume 25:Number 2(2016:Mar.)
• Page Start: 213
• Page End: 221
• Publication Date: 2015-02-24
• Subjects: Primary 03C98, -- Secondary 05C63, -- 28E15; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548315000048
• Languages: English
• ISSNs: 0963-5483

Abstract

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 ( 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.