SMF

Exposé Bourbaki 1153 : Normalité asymptotique des vecteurs propres d'un graphe régulier aléatoire d'après Ágnes Backhausz et Balázs Szegedy

Exposé Bourbaki 1153 : Asymptotic normality of eigenvectors of $d$-regular random graphs, after Ágnes Backhausz et Balázs Szegedy

Charles BORDENAVE
Exposé Bourbaki 1153 : Normalité asymptotique des vecteurs propres d'un graphe régulier aléatoire d'après Ágnes Backhausz et Balázs Szegedy
  • Consulter un extrait
  • Année : 2020
  • Tome : 422
  • Format : Électronique
  • Langue de l'ouvrage :
    Français
  • Class. Math. : 05C80; 60B20
  • Pages : 109-147
  • DOI : 10.24033/ast.1132

Soit $P$ l'ensemble des matrices symétriques de taille $n$ avec des entrées dans $\{0, 1\}$, nulles sur la diagonale et dont la somme de chaque ligne est égale à $d$ (avec $dn$ pair). Un élément de $P$ est la matrice d'adjacence d'un graphe simple à $n$ sommets et $d$-régulier. Soient $A$ une matrice aléatoire uniforme sur $P$ et $v$ un vecteur propre orthogonal au vecteur constant. Dans l'asymptotique où $d$ est fixé et $n$ tend vers l'infini, Backhausz et Szegedy ont notamment montré que la distribution des entrées du vecteur $v$ est proche en loi d'une gaussienne. Leur preuve se base sur la convergence locale des graphes et la théorie de l'information.

Let $P$ be the set of symmetric matrices of size $n$ with entries in $\{0, 1\}$, zeroes on the diagonal, and row sums equal to $d$ (with $dn$ even). An element of $P$ is the adjacency matrix of a simple $d$-regular graph on $n$ vertices. Let $A$ be a uniform random matrix on $P$ and $v$ be an eigenvector orthogonal to the constant vector. In the asymptotic range where $d$ is fixed and $n$ tends to infinity, Backhausz and Szegedy have proved that the law of the distribution of entries of the vector $v$ is close to that of a Gaussian. Their proof is based on local convergence of graphs and information theory

Graphes réguliers aléatoires, vecteurs propres, fonctions propres aléatoires gaussiennes
Random regular graphs, eigenvectors, Gaussian random waves
Prix
Adhérent 7 €
Non-Adhérent 10 €
Quantité
- +