Multi angle

H 1 Local limits and connectivity

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

      Langue : Anglais
      Date de publication : 04/02/15
      Date de captation : 20/01/15
      Collection : Research talks ; Combinatorics
      Format : quicktime ; audio/x-aac
      Durée : 00:46:34
      Domaine : Combinatorics
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      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

    Citation Data

    DOI : 10.24350/CIRM.V.18671703
    Cite this video as: 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


    1. Benjamini, I., & Schramm, O. (2001). Recurrence of distibutional limits of finite planar graphs. Electronic Journal of Probability, 6(23), 13 p. - http://dx.doi.org/10.1214/EJP.v6-96

    2. Lovász, L. (2012). Large networks and graph limits. Providence, RI: American Mathematical Society. (Colloquium Publications, 60) - https://www.zbmath.org/?q=an:1292.05001

    3. Lovász, L., & Szegedy, B. (2006). Limits of dense graph sequences. Journal of Combinatorial Theory. Series B, 96(6), 933–957 - http://dx.doi.org/10.1016/j.jctb.2006.05.002

    4. Nesetril, J., & Ossona de Mendez, P. (2012). A model theory approach to structural limits. Commentationes Mathematicæ Universitatis Carolinae, 53(4), 581–603 - https://www.zbmath.org/?q=an:1274.05464

    5. Nesetril, J., & Ossona de Mendez, P. (2013). A unified approach to structural limits, and limits of graphs with bounded tree-depth. - http://arxiv.org/abs/1303.6471

    6. Nesetril, J., & Ossona de Mendez, P. (2013). Modeling limits in hereditary classes: reduction and application to trees. - http://arxiv.org/abs/1312.0441

Titres de périodiques et e-books électroniques (Depuis le CIRM)

Ressources Electroniques

Books & Print journals

Recherche avancée