SMF

Exposé Bourbaki 1202 : Convergence forte du spectre de permutations aléatoires et graphes presque Ramanujan [d'après Charles Bordenave et Benoît Collins]

Exposé Bourbaki 1202 : Strong convergence of the spectrum of random permutations and almost-Ramanujan graphs [after Charles Bordenave and Benoît Collins]

Mylène MAÏDA
Exposé Bourbaki 1202 : Convergence forte du spectre de permutations aléatoires et graphes presque Ramanujan [d'après Charles Bordenave et Benoît Collins]
  • Consulter un extrait
  •  
                
  • Année : 2023
  • Tome : 446
  • Format : Électronique
  • Langue de l'ouvrage :
    Anglais
  • Class. Math. : 60B20, 15B52, 46L54, 05C48
  • Pages : 199-223
  • DOI : 10.24033/ast.1211

Un graphe fini est dit Ramanujan si sa matrice d'adjacence possède un trou spectral maximal, ce qui lui assure d'excellentes propriétés de graphe expanseur. À partir d'une famille de permutations aléatoires, Bordenave et Collins construisent une suite de graphes aléatoires presque Ramanujan. Cette propriété peut dans ce cas se reformuler en termes de convergence forte en probabilités libres. L'exposé sera l'occasion de présenter les résultats connus de convergence forte et quelques-unes de leurs applications. Nous insisterons par ailleurs sur un outil important de leur preuve, l'opérateur non-backtracking associé à l'opérateur d'adjacence pondéré d'un graphe. Nous expliquerons comment le spectre de ces deux opérateurs est relié et évoquerons son usage pour l'étude des graphes aléatoires.

A finite graph is said to be Ramanujan if the spectral gap of its adjacency matrix is maximal,  which makes it an excellent expander graph. From a family of random permutations, Bordenave and Collins construct a sequence of random graphs that are almost-Ramanujan. This property can in this case be reformulated in terms of strong convergence in free probability theory. The talk will be an opportunity to present known results on strong convergence and some of their applications. We will also insist on an important tool for their proof, the non-backtracking operator associated to the weighted adjacency operator of a graph. We will explain the link between the spectrum of the two operators and discuss the use of the non-backtracking operator in the study of random graphs.

Probabilités libres, permutations aléatoires, matrices aléatoires, graphes aléatoires, graphes expanseurs, liberté asymptotique forte, opérateur non-backtracking
Free probability, random permutations, random matrices, random graphs, expander graphs, strong asymptotic freeness, non-backtracking operators

Électronique
Electronic
Prix public Public price 10.00 €
Prix membre Member price 7.00 €
Quantité
Quantity
- +