Quelques conséquences de la convergence locale faible pour les graphes aléatoires

TL;DRAbstract

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 distr

Chat with Paper

AI Agents for this Paper