SMF

Une nouvelle démonstration du théorème de la seconde valeur propre de Friedman et son extension aux revêtements aléatoires

A new proof of Friedman's second eigenvalue theorem and its extension to random lifts

Charles BORDENAVE
Une nouvelle démonstration du théorème de la seconde valeur propre de Friedman et son extension aux revêtements aléatoires
  • Consulter un extrait
  • Année : 2020
  • Fascicule : 6
  • Tome : 53
  • Format : Électronique
  • Langue de l'ouvrage :
    Anglais
  • Class. Math. : 05C80, 60B20, 68R10
  • Pages : 1393-1439
  • DOI : 10.24033/asens.2450

Il a été conjecturé par Alon et démontré par Friedman qu'un graphe $d$-régulier aléatoire a un trou de spectre asymptotiquement maximal, ou, plus précisément, que la plus grande valeur propre non-triviale de sa matrice d'adjacence est au plus $2\sqrt{d-1} +o(1)$ avec probabilité tendant vers un lorsque la taille du graphe tend vers l'infini. Nous donnons une nouvelle preuve de ce résultat. Nous étudions aussi des questions reliées sur les $n$-revêtements aléatoires d'un graphe et améliorons un résultat récent de Friedman and Kohler.

It was conjectured by Alon and proved by Friedman that a random $d$-regular graph has nearly the largest possible spectral gap, or, more precisely, that the largest absolute value of the non-trivial eigenvalues of its adjacency matrix is at most $2\sqrt{d-1} +o(1)$ with probability tending to one as the size of the graph tends to infinity. We give a new  proof of this statement.  We also study related questions on random $n$-lifts of graphs  and improve a recent result by Friedman and Kohler.

Graphe régulier aléatoire, trou spectral, revêtement aléatoire
Random regular graphs, spectral gap, random lift
Prix
Adhérent 14 €
Non-Adhérent 20 €
Quantité
- +