En poursuivant votre navigation sur ce site, vous acceptez l'utilisation d'un simple cookie d'identification. Aucune autre exploitation n'est faite de ce cookie. OK
1

Local limits and connectivity

Sélection Signaler une erreur
Multi angle
Auteurs : Ossona de Mendez, Patrice (Auteur de la Conférence)
CIRM (Editeur )

Loading the player...

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

Codes MSC :
03C13 - Finite structures [See also 68Q15, 68Q19]
03C98 - Applications of model theory
05Cxx - Graph theory

    Informations sur la Vidéo

    Réalisateur : Hennenfent, Guillaume
    Langue : Anglais
    Date de publication : 04/02/15
    Date de captation : 20/01/15
    Sous collection : Research talks
    arXiv category : Combinatorics
    Domaine : Combinatorics
    Format : MP4 (.mp4) - HD
    Durée : 00:46:34
    Audience : Researchers
    Download : https://videos.cirm-math.fr/2015-01-20_Mendez.mp4

Informations sur la Rencontre

Nom de la rencontre : International workshop on graph decomposition / Rencontre internationale sur les méthodes de décomposition de graphes
Organisateurs de la rencontre : Kreutzer, Stephan ; Paul, Christophe ; Trotignon, Nicolas ; Wollan, Paul
Dates : 19/01/15 - 23/01/15
Année de la rencontre : 2015

Données de citation

DOI : 10.24350/CIRM.V.18671703
Citer cette vidéo: Ossona de Mendez, Patrice (2015). Local limits and connectivity. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18671703
URI : http://dx.doi.org/10.24350/CIRM.V.18671703

Bibliographie



Sélection Signaler une erreur