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

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