Graphes aléatoires peu denses : de spécifications locales vers des phénomènes globaux

Sparse random graphs : from local specifications to global phenomena Cette thèse est consacrée à l'étude de différents graphes aléatoires, définis par des propriétés locales (comme la distribution des degrés des sommets ou la probabilité que deux sommets donnés soient reliés par une arête), et dont on cherche à déterminer des caractéristiques globales, notamment leur géométrie et le comportement de marches aléatoires. Elle se compose de trois parties indépendantes. À chaque fois, le graphe aléatoire étudié admet un arbre comme limite locale, et une comparaison fine entre l'arbre et le graphe permet de transposer des propriétés du premier au second. * La première partie (Chapitre 2) porte sur la limite d'échelle d'un graphe aléatoire critique, un modèle de configuration avec des degrés indépendants et distribués selon une même loi de puissance à queue lourde : elle a une variance, mais pas de troisième moment. Il était connu que les plus grandes composantes connexes de ce graphe ont une taille Θ(n^a) pour un graphe à n sommets, le paramètre a dépendant du modèle. On montre que leur structure converge vers une version biaisée d'un arbre aléatoire continu particulier, l'arbre stable, auquel on rajoute un nombre fini de cycles. * La seconde partie (Chapitre 3) est consacrée au champ libre gaussien sur des graphes aléatoires d-réguliers. On étudie la percolation du champ libre au-dessus d'un niveau fixé. Si on baisse ce niveau en-dessous d'un certain seuil critique, on établit l'émergence avec grande probabilité d'une unique composante connexe géante englobant une proportion positive des sommets, entourée d'ilôts de taille logarithmique, tandis que seuls ces derniers survivent au-dessus du seuil critique. On montre alors que ce grand continent admet de remarquables similitudes avec la composante géante d'un graphe aléatoire célèbre, le modèle d'Erd's-Rényi. * La troisième partie (Chapitre 4) traite de marches aléatoires sur des relèvements aléatoires ("random lifts") d'un graphe quelconque donné. Ces relèvements sont des graphes peu denses mais avec de bonnes propriétés de connectivité et une structure assez régulière, l'arbre associé étant périodique. On prouve que la marche aléatoire sur ces graphes admet un cutoff, c'est-à-dire qu'il y a une transition brusque entre le moment où le marcheur est encore localisé autour de son point de départ, et celui où on a définitivement perdu sa trace.