Graphe de Ramanujan
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/db/Pappus_graph.svg/220px-Pappus_graph.svg.png)
Un graphe de Ramanujan, nommé d'après Srinivasa Ramanujan, est un graphe régulier dont le trou spectral (spectral gap) est presque aussi grand que possible. De tels graphes sont d'excellents graphes expanseurs. Autrement dit, il s'agit d'une famille de graphes où chaque sommet a un même degré (régulier) et où les deux valeurs propres les plus élevées ont une différence presque aussi grande que possible.
Parmi les graphes de Ramanujan, on compte les cliques, les bipartis complets et le graphe de Petersen. Comme le fait remarquer M. Ram Murty[1], les graphes de Ramanujan « regroupent diverses branches des mathématiques, telles que la théorie des nombres, la théorie des représentations et la géométrie algébrique ».
Définition
[modifier | modifier le code]Soit un graphe connexe -régulier ayant sommets, et soient les valeurs propres de la matrice d'adjacence de (voir théorie spectrale des graphes). Comme est connexe et -régulier, ses valeurs propres vérifient . À chaque fois qu'il existe tel que , on définit
Un graphe -régulier est un graphe de Ramanujan si est défini et vaut .
Extrémalité des graphes de Ramanujan
[modifier | modifier le code]Pour et fixés, le graphe de Ramanujan -régulier à sommets minimise . Si est un graphe -régulier de diamètre , un théorème de Noga Alon[2] donne :
Lorsque est -régulier et connexe sur au moins trois de ses sommets, , d'où . Soit l'ensemble de tous les graphes -réguliers ayant au moins sommets. Comme le diamètre minimal de ces graphes tend vers l'infini pour fixé et tendant vers l'infini, le théorème de Nilli implique le théorème d'Alon et Boppana, démontré plus tôt, qui affirme :
Bauwesen
[modifier | modifier le code]La construction de graphes de Ramanujan se fait souvent à l'aide de graphes de Ramanujan -réguliers, pour tout premier et tel que p ≡ 1 (mod 4). Leur preuve utilise la conjecture de Ramanujan, ce qui a donné leur nom aux graphes. Morgenstern étendit la construction à toutes les puissances de nombres premiers impairs.
Notes et références
[modifier | modifier le code]- (en) M. Ram Murty, « Ramanujan Graphs », J. Ramanujan Math. Soc., vol. 18, no 1, , p. 1-20 (lire en ligne)
- (en) Nilli Alon, « On the second eigenvalue of a graph », Discrete Mathematics, vol. 91, no 2, , p. 207-210 (lire en ligne)
Voir aussi
[modifier | modifier le code]Bibliographie
[modifier | modifier le code]- (en) Giuliana Davidoff, Peter Sarnak et Alain Valette, Elementary number theory, group theory and Ramanjuan graphs, vol. 55, Cambridge University Press, coll. « LMS student texts », (ISBN 0-521-53143-8, OCLC 50253269)
- (en) Alexander Lubotzky, R. Phillips, Peter Sarnak, « Ramanujan graphs », Combinatorica, vol. 8, , p. 261–277 (DOI 10.1007/BF02126799)
- (en) Moshe Morgenstern, « Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q », J. Combinatorial Theory, Series B, vol. 62, , p. 44–62 (DOI 10.1006/jctb.1994.1054)
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Ramanujan graph » (voir la liste des auteurs).