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

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.This thesis is devoted to the study of different random graphs, defined by local properties (such as the distribution of the degrees of the vertices, or the probability that two given vertices share an edge). We investigate some of their global characteristics, in particular their geometry and the behaviour of random walks. It consists of three independent parts. In each of them, the local limit of the random graph is a tree, and a fine comparison between the tree and the graph allows to implement properties of the former on the latter. * The first part (Chapter 2) is about the scaling limit of a critical random graph, more precisely a configuration model with independent and identically distributed degrees having power-law heavy tail behaviour: there is a variance, but no third moment. It was known that the largest connected components of this graph scale like Θ(n^a ) if the graph is on n vertices, for some model-dependent constant a. We prove that their structure converges to a biased version of a particular random R-tree, the stable tree, to which one adds a finite number of cycles. * The second part (Chapter 3) is devoted to the gaussian free field on random d-regular graphs. We study its percolation above a fixed level. If this level is below a certain critical threshold, we establish the emergence with high probability of a unique giant component containing a positive proportion of the vertices, surrounded by islets of logarithmic size, while only the latter survive above the critical threshold. We show that this big continent shares remarkable similarities with the giant component of a famous random graph, the Erdös-Rényi model. * The third part (Chapter 4) deals with random walks on random lifts of an arbitrary base graph. Random lifts are sparse graphs with good connectivity properties and a regular structure, the associated tree being periodic. We prove that the random walk on these graphs admits a cutoff, i.e. there is a brutal transition between the time when it is still localised around its starting point, and the time when we have completely lost its track