Graphe de Ramanujan

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

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

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

Pour ${\displaystyle d}$ et ${\displaystyle n}$ fixés, le graphe de Ramanujan ${\displaystyle d}$-régulier à ${\displaystyle n}$ sommets minimise ${\displaystyle \lambda (G)}$. Si ${\displaystyle G}$ est un graphe ${\displaystyle d}$-régulier de diamètre ${\displaystyle m}$, un théorème de Noga Alon[2] donne :

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

Lorsque ${\displaystyle G}$ est ${\displaystyle d}$-régulier et connexe sur au moins trois de ses sommets, ${\displaystyle |\lambda _{1}|<d}$, d'où ${\displaystyle \lambda (G)\geq |\lambda _{1}|}$. Soit ${\displaystyle {\mathcal {G}}_{n}^{d}}$ l'ensemble de tous les graphes ${\displaystyle d}$-réguliers ${\displaystyle G}$ ayant au moins ${\displaystyle n}$ sommets. Comme le diamètre minimal de ces graphes ${\displaystyle {\mathcal {G}}_{n}^{d}}$ tend vers l'infini pour ${\displaystyle d}$ fixé et ${\displaystyle n}$ 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 :

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

La construction de graphes de Ramanujan se fait souvent à l'aide de graphes de Ramanujan ${\displaystyle p+1}$-réguliers, pour tout ${\displaystyle 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 à toutes les puissances de nombres premiers impairs.