m

Documents  Ossona de Mendez, Patrice | enregistrements trouvés : 3

O
     

-A +A

P Q

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;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.

- xxiii; 457 p.
ISBN 978-3-642-27874-7

Algorithms and combinatorics , 0028

Localisation : Ouvrage RdC (NESE)

analyse combinatoire # matrice éparse # complexité de calcul # densité # sparsité # arbre enraciné # mineur # théorie des graphes # homomorphisme # théorie des modèles # logique du premier ordre

05-02 ; 05C05 ; 05C10 ; 05C15 ; 05C42 ; 05C60 ; 05C62 ; 05C65 ; 05C75 ; 05C78 ; 05C83 ; 05C85 ; 05C90 ; 03C13 ; 68R10 ; 90C35

... Lire [+]

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 [+]

Z