Chapitre 8 Graphes de Ramanujan
Ces graphes sont en fait des familles de graphes, ayant la propriété
que lorsque le degré d est fixe et l'ordre tend vers l'infini le spectre
(hormis les valeurs propres d et éventuellement -d)
tend à se concentrer dans l'intervalle -2Ö(d-1),2Ö(d-1).
C'est évidemment le cas pour la famille des cycles--- trop évidemment pour être
intéressant.
8.1 Description
8.1.1 Quaternions
Si on a un anneau commutatif R, on peut donner à R4 une structure
d'algèbre associative sur R, avec la base 1,i,j,k et la multiplication
définie par bilinéarité à partir de i2=j2=k2=-1 et ij=k=-ji, jk=i=-kj,
ki=j=-ik. C'est l'algèbre des quaternions sur R.
La norme de a+bi+cj+dk est a2+b2+c2+d2.
Il y a isomorphisme entre les quaternions sur 
q et les matrices
2× 2 sur q avec leur multiplication ordinaire
peut être obtenu de la façon suivante :
on choisit une solution à a2+b2=-1 dans q. On peut alors associer
aux quaternions i,j,k les matrices suivantes :
La norme correspond alors au déterminant de la matrice.
Si q=1mod 4, il y a un élément a de q avec a2=-1, on peut donc
prendre b=0.
On forme le monoïde des quaternions à coefficients entiers dont la norme est
une puissance de p, avec p premier congru à 1 modulo 4.
Il a un sous-monoïde formé des quaternions avec
la partie réelle impaire et les trois autres paires. On quotiente
ce monoïde par le sous-monoïde des ± pk. On obtient ainsi un groupe,
qui a pour générateur un ensemble symétrique à p+1 éléments.
Le graphe de Cayley de ce groupe, avec ce générateur, est un arbre.
Pour revenir au cas fini, on calcule les coefficients modulo q où q est
un nombre premier différent de p.
On obtient ainsi un groupe à q3-q ou q3-q/2
éléments, isomorphe au groupe PGL(2,q) ou PSL(2,q)
de matrices 2×2 sur le corps q à q éléments, modulo
l'homothétie, selon que p est un non-résidu ou un résidu quadratique
modulo q, avec une famille génératrice à p+1 éléments, qui sont
tous distincts dès que q est assez grand (q>2Ö(p) suffit).
Si p est un non-résidu, le graphe est biparti.
Observons en outre que l'ensemble des quaternions à coefficients entiers de
norme p est stable par conjugaison par les 48 éléments du groupe
de quaternions rationnels :
±1,± i,± j,± k, (cela fait 8) ou ±1± i,± i± j (et 24 de
plus) ou ± 1± i± j± k (et encore 16). Ce qui donne des orbites
d'ordre divisant 24.
8.1.2 Variante
On prend p congru à 3 modulo 4, et les quaternions avec la partie réelle
de parité opposée à celle des trois autres. On obtient également
ainsi un graphe de degré p+1 qui se replie modulo q etc.
8.1.3 Exemples
Pour p=5 et q=3, on trouve un graphe biparti de degré 6, diamètre 3,
arête-transitif à 24 sommets.
Il est isomorphe au graphe de Cayley du groupe symétrique 
4
avec le générateur formé des 6 permutations cycliques.
Pour p=7 et q=3, on trouve un graphe de diamètre 2, de degré
8, arête-transitif à 12 sommets. Il est isomorphe
au graphe de Cayley du groupe symétrique
4, avec le générateur formé des 8 permutations d'ordre 3.
C'est le triparti complet K4,4,4.
Pour p=11 et q=3, on a le biparti K12,12.
Pour p=3 et q=5, on obtient un graphe à 120 sommets, de degré 4,
diamètre 6, biparti, arête-transitif.
Pour p=3 et q=7, un graphe à 336 sommets, degré 4, biparti,
arête-transitif, diamètre 6, maille 6.
Pour p=11 et q=5, on obtient un graphe à 60 sommets, de degré 12,
arête-transitif, et diamètre 3.
Pour p=13 et q=5, on a un graphe biparti de degré 14, diamètre 3,
à 120 sommets, mais pas arête-transitif, car l'arête provenant de
3+2i se trouve dans 33 cycles de longueur 4, alors que
celle provenant de 1+2(i+j+k) se trouve dans 27 cycles de longueur 4,