Graphe de Ramanujan

Un graphe de Ramanujan, nommé d'après Srinivasa Ramanujan, est un graphe régulier dont le gap spectral est presque aussi large que possible. De tels graphes sont d'excellents graphes extenseurs. Autrement dit, il s'agit d'une famille de graphes où chaque sommet a un même degré (régulier) et 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 biparti complet $K_{n,n}$ et le graphe de Petersen. Comme le fait remarquer le de Murty, 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

Soit $G$ un graphe connecté $d$-régulier ayant $n$ sommets, et soient $\lambda _{0}\geq \lambda _{1}\geq \ldots \geq \lambda _{n-1}$ les valeurs propres de la matrice d'adjacence de $G$ (voir théorie spectrale des graphes). Comme $G$ est connecté et $d$-régulier, ses valeurs propres vérifient $d=\lambda _{0}\geq \lambda _{1}\geq \ldots \geq \lambda _{n-1}\geq -d$. A chaque fois qu'il existe $\lambda _{i}$ tel que $|\lambda _{i}|<d$, on définit

$\lambda (G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|.\,$

Un graphe $d$-régulier $G$ est un graphe de Ramanujan si $\lambda (G)$ est définit et vaut $\lambda (G)\leq 2{\sqrt {d-1}}$.

Extremalité des graphes de Ramanujan

Pour $d$ fixé et $n$ n, le graphe de Ramanujan $d$-régulier à $n$ sommets Ramanujan minimise $\lambda (G)$. Si $G$ est un graphe $d$-régulier de diamètre $m$, un théorème d'Alon Nilli donne :

$\lambda _{1}\geq 2{\sqrt {d-1}}-{\frac {2{\sqrt {d-1}}-1}{m}}.$

Lorsque $G$ est $d$-régulier et connecté sur au moins trois de ses sommets, $|\lambda _{1}|<d$, d'où $\lambda (G)\geq \lambda _{1}$. Soit ${\mathcal {G}}_{n}^{d}$ l'ensemble de tous les graphes $d$-réguliers $G$ ayant au moins $n$ sommets. Comme le diamètre minimal de ces graphes ${\mathcal {G}}_{n}^{d}$ tend vers l'infini pour $d$ fixé et $n$ tendant vers l'infini, le théroème de Nilli implique le théorème d'Alon et Boppana, démontré plus tôt, qui affirme :

$\lim _{n\to \infty }\inf _{G\in {\mathcal {G}}_{n}^{d}}\lambda (G)\geq 2{\sqrt {d-1}}.$

Construction

La construction de graphes de Ramanujan se fait souv de graphes de Ramanujan $p+1$-réguliers, pour tout $p$ 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 à tous les nombres premiers.

Références

• (en) Guiliana Davidoff, Elementary number theory, group theory and Ramanjuan graphs, vol. 55, Cambridge University Press, coll. « LMS student texts », 2003 (ISBN 0-521-53143-8, OCLC 50253269)
• Alexander Lubotzky, R. Phillips, Peter Sarnak, « Ramanujan graphs », Combinatorica, vol. 8,‎ 1988, p. 261–277 (DOI 10.1007/BF02126799)
• Moshe Morgenstern, « Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q », J. Combinatorial Theory, Series B, vol. 62,‎ 1994, p. 44–62 (DOI 10.1006/jctb.1994.1054)

Liens externes

• État de l'art par M. Ram Murty