Déposez votre fichier ici pour le déplacer vers cet enregistrement.
Combinatorics
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
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 ...
03C13 ; 03C98 ; 05Cxx
... Lire [+]
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
- v; 108 p.
ISBN 978-1-4704-4065-7
Memoirs of the American Mathematical Society , 1272
Localisation : Collection 1er étage
graphe et structure relationnelle # limite du graphe # limite structurelle # mesure du radon # espace de Stone # théorie du modèle # logique du premier ordre # graphe mesurable
03C13 ; 03C98 ; 05C99 ; 06E15 ; 28C05
... Lire [+]