Résumé : The theory of graph (and structure) convergence gained recently a substantial attention. Various notions of convergence were proposed, adapted to different contexts, including Lovasz et al. theory of dense graph limits based on the notion of left convergence and Benjamini-Schramm theory of bounded degree graph limits based on the notion of local convergence. The latter approach can be extended into a notion of local convergence for graphs (stronger than left convegence) as follows: A sequence of graphs is local convergent if, for every local first-order formula, the probability that the formula is satisfied for a random (uniform independent) assignment of the free variables converge as n grows to infinity. In this talk, we show that the local convergence of a sequence of graphs allows to decompose the graphs in the sequence in a coherent way, into concentration clusters (intuitively corresponding to the limit non-zero measure connected components), a residual cluster, and a negligible set. Also, we mention that if we consider a stronger notion of local-global convergence extending Bollobas and Riordan notion of local-global convergence for graphs with bounded degree, we can further refine our decomposition by exhibiting the expander-like parts.

graphs - structural limit - graph limit - asymptotic connectivity