- Actualités
- » Annonce
Leçons sur les graphes épars
LIAFA - Salle : 6 A 92 (6ème étage, plateau A)
-
175, rue du Chevaleret
- 75013 Paris
Des leçons sur les graphes épars (expansion bornée, graphes nulle part dense) données par Patrice Ossona de Mendez, du CAMS, sont organisées dans le cadre du projet ANR Heredia.
Différentes approches descriptives des réseaux complexes ont été considérées, soit en considérant des notions telles que les transitions de phase, la renormalisation, les systèmes désordonnés, la percolation ou les états critiques auto-organisés, soit en s’appuyant sur la
théorie des structures relationnelles en général, et sur la théorie des graphes et hypergraphes en particulier.
Dans ce contexte, le célèbre lemme de régularité de Szemerédi a ouvert la voie à l’approximation des grands réseaux, à une notion de convergence inductive, et au property testing. Néanmoins, ce point de vue est centré sur les structures « denses », dans le sens où la proportion des relations présentes (par rapport à l’ensemble des toutes les relations potentiellement existantes) au sein d’une structure pas trop proche de la structure vide doit être suffisamment éloignée de zéro.
À l’occasion de cette série d’exposés, nous étudierons en profondeur les propriétés structurelles des graphes épars, au travers notamment de la notion de mineurs superficiels, de décompositions de faible profondeur d’arbre, de propriétés d’indépendance en relation avec la logique du premier ordre, de dualités restreintes d’homomorphismes et de statistiques de motifs. Nous insisterons sur une taxonomie des classes de graphes basées sur un saut qualitatif des propriétés structurelles (classes nulle part denses / classes quelque part denses ; classes d’expansion bornée). Nous considérerons également nombres d’applications théoriques et algorithmiques.
La participation est gratuite, mais le nombre de places étant limité il est nécessaire de s’inscrire auprès des organisateurs.
Horaires :
le 6 octobre : 10h15-11h15 puis 11h30-12h30 puis 14h-15h
le 7 octobre : 10h15-11h15 puis 11h30-12h30 puis 14h-15h
le 8 octobre : 10h15-11h15 puis 11h30-12h30
Différentes approches descriptives des réseaux complexes ont été considérées, soit en considérant des notions telles que les transitions de phase, la renormalisation, les systèmes désordonnés, la percolation ou les états critiques auto-organisés, soit en s’appuyant sur la
théorie des structures relationnelles en général, et sur la théorie des graphes et hypergraphes en particulier.
Dans ce contexte, le célèbre lemme de régularité de Szemerédi a ouvert la voie à l’approximation des grands réseaux, à une notion de convergence inductive, et au property testing. Néanmoins, ce point de vue est centré sur les structures « denses », dans le sens où la proportion des relations présentes (par rapport à l’ensemble des toutes les relations potentiellement existantes) au sein d’une structure pas trop proche de la structure vide doit être suffisamment éloignée de zéro.
À l’occasion de cette série d’exposés, nous étudierons en profondeur les propriétés structurelles des graphes épars, au travers notamment de la notion de mineurs superficiels, de décompositions de faible profondeur d’arbre, de propriétés d’indépendance en relation avec la logique du premier ordre, de dualités restreintes d’homomorphismes et de statistiques de motifs. Nous insisterons sur une taxonomie des classes de graphes basées sur un saut qualitatif des propriétés structurelles (classes nulle part denses / classes quelque part denses ; classes d’expansion bornée). Nous considérerons également nombres d’applications théoriques et algorithmiques.
La participation est gratuite, mais le nombre de places étant limité il est nécessaire de s’inscrire auprès des organisateurs.
Horaires :
le 6 octobre : 10h15-11h15 puis 11h30-12h30 puis 14h-15h
le 7 octobre : 10h15-11h15 puis 11h30-12h30 puis 14h-15h
le 8 octobre : 10h15-11h15 puis 11h30-12h30
Date
- du mercredi 6 octobre 2010 à 10h15 au vendredi 8 octobre 2010 à 12h30
Contact
- Ossona de Mendez (pom@ehess.fr)
Url de référence