Documentation Documentation
Identifiant IdRef : 226712400
Notice de type Rameau

Point d'accès autorisé

Informations

Langue d'expression : Anglais
Date de naissance :  2011
Note publique d''information : 
Dans la limite “diluée” où les nombres d'arêtes et de sommets divergent de manière comparable, on s'attend à ce que le comportement asymptotique de nombreux invariants de graphes ne dépende que de statistiques purement locales. Cette heuristique provient de l'étude thermodynamique de certains systèmes désordonnés en physique statistique, où la contribution microscopique de chaque particule est insensible aux perturbations lointaines. Mathématiquement, une telle absence d'interactions à longue portée se traduit par la continuité de l'invariant vis-à-vis de la topologie de la convergence locale faible. En particulier, l'invariant admettra une limite déterministe le long de la plupart des suites de graphes aléatoires classiques, et pourra être efficacement approximé par des algorithmes locaux et distribués, indépendamment de la taille totale du système. Dans cette thèse, nous étudions quatre invariants de graphes qui jouent un rôle essentiel en théorie comme dans les applications : la distribution spectrale empirique, la dimension du noyau de la matrice d'adjacence, la taille d'un couplage maximum, et le polynôme énumérant certaines familles de sous-graphes couvrants. Nous montrons qu'il existe une unique manière localement cohérente d'étendre chacune de ces notions aux limites locales faibles de graphes finis, et que ce prolongement est continu. Pour les modèles de graphes aléatoires classiques, les équations de cohérence locale se simplifient en une équation aux distributions que nous résolvons explicitement. Cela conduit à de nouvelles formules asymptotiques, ainsi qu'à la simplification, l'unification et la généralisation de divers résultats jusqu'alors isolés.

Notices d'autorité liées

Autres identifiants

Utilisation dans Rameau

Le point d'accès peut être employé dans un point d'accès sujet

... Références liées : ...