\magnification\magstep1
\font\bigbf=cmbx12
\font\bigsl=cmsl12
\def\l{\lambda}
\def\Perm{\mathop{\rm Perm}\nolimits}
\def\mod{\mathop{\rm mod}\nolimits}
\def\sharp{{\tt \#}}
{}\quad{}
\bigskip
\centerline{\bigbf Graphes de Moore}
\bigskip
\bigskip
\centerline{\bigsl S.~Duzhin, Universit\'{e} de Pereslavl}
\smallskip
\centerline{\tt duzhin@botik.ru}
\bigskip
\bigskip
 
Un graphe de Moore est un graphe r\'{e}gulier de diam\`{e}tre 2
et de degr\'{e} $k$ ayant $k^2+1$ sommets.
On sait qu'un tel graphe ne peut exister que pour
les valeurs suivantes de $k$: $k=2$, 3, 7 et 57
(th\'{e}or\`{e}me de Hoffman et Singleton [1]).
On conna\^{\i}t la structure des graphes de Moore de degr\'{e} $k= 2$, 3 et 7.
On ne sait rien dans le cas $k=57$.

Je dirai quelques mots sur l'origine de ce probleme,
je donnerai une d\'{e}monstration simple du th\'{e}or\`{e}me
de Hoffman et Singleton et je parlerai de la g\'{e}om\'{e}trie
des graphes de Moore de degr\'{e} 3 (dit {\it graphe de Petersen\/})
et de degr\'{e} 7 (dit {\it Hoffman--Singleton\/}).
De plus, on verra l'importance des notions primaires
de la topologie alg\'{e}brique (espace fibr\'{e}, rev\^{e}tement,
groupe de monodromie) dans ce sujet.
 
\beginsection D\'{e}finitions
 
\indent
Par un {\it graphe\/}, on entend un graphe non dirig\'{e},
sans lacets ni ar\^{e}tes multiples. Un graphe est dit {\it r\'{e}gulier\/}
de degr\'{e} $k$, si tout sommet est incident avec exactement $k$ ar\^{e}tes.
La {\it distance} entre deux points est la longueur minimale d'un chemin
qui les r\'{e}unit. Le diam\`{e}tre du graphe est la distance maximale
entre deux de ses sommets.

Par example, un circuit de $2k+1$ sommets est un graphe r\'{e}gulier
de degr\'{e} 2 et diam\`{e}tre $k$.

On voit tout de suite que le nombre de sommets dans un graphe
de degr\'{e} $k$ et diam\`{e}tre 2 ne peut jamais surpasser $k^2+1$.
En effet, choisissons un sommet quelconque $v$, alors le nombre
des sommets voisins de $v$ est $k$ et le nombre des sommets \'{a} distance 2
de $v$ est inf\'{e}rieur ou \'{e}gal \`{a} $k(k-1)$.
L'\'{e}galit\'{e} tient si et seulement si tous les points
\`{a} distance 1 et 2 de $v$ sont distincts. Dans ce cas,
le nombre total de sommets devient $1+k+k(k-1) = k^2+1$.
 
On peut exprimer le raisonnement ci-dessus de la mani\`{e}re
suivante:
\smallskip
 
{\bf Proposition 1.}
{\sl Un graphe r\'{e}gulier de degr\'{e} $k$ avec $k^2+1$ sommets est un
graphe de Moore si et seulement si il n'a pas de cycles de longueur 3 et 4.}
\smallskip
 
{\sl Remarque.\/} On peut \'{e}galement introduire la notion du graphe de Moore
de diam\`{e}tre $d>2$, mais un th\'{e}or\`{e}me simple affirme qu'un
tel graphe est toujours ou bien un circuit ou bien un graphe de Moore de
diam\`{e}tre 2. Le probl\`{e}me g\'{e}n\'{e}ral comprenant ce des
graphes de Moore est le probleme des {\it grands graphes de
degr\'{e} et diam\`{e}tre donn\'{e}s\/} (voir [3] et les r\'{e}f\'{e}rences
l\`{a}-dedans).
 
\beginsection Th\'{e}r\`{e}me fondamentale
 
\indent
{\bf Th\'{e}or\`{e}me} (Hoffman et Singleton.)
{\sl Le degr\'{e} d'un graphe de Moore ne peut \^{e}tre \'{e}gal qu'\`{a} 
une des valeurs suivantes: 2, 3, 7 et 57.}
\smallskip
 
{\bf D\'{e}monstration.}
Soit $G$ un graphe de Moore de degr\'{e} $k$.
D\'{e}notons par $A$ sa matrice associe\'{e}, $A_{i,j}=1$ si les sommets
num\'{e}ro $i$ et $j$ sont adjacents, 0 autrement.
Soit $B$ la matrice de distance 2, c'est-\`{a}-dire
$B_{i,j}=1$ si la distance entre les sommets $i$ et $j$ est 2,
$B_{i,j}=0$ autrement.
Si encore $E$ est la matrice unit\'{e} (matrice de distance 0),
on a alors $E+A+B=I$ o\`{u} $I$ est la matrice avec tous
\'{e}l\'{e}ments \'{e}gaux \`{a} 1.
 
La proposition 1 entra\^{\i}ne les deux lemmes suivants:
\smallskip
 
{\bf Lemme 1.} $A^2 = kE + B$.
\smallskip
 
{\bf Lemme 2.} $AB = (k-1)A + (k-1)B$.
\smallskip

\noindent
--- et l'on en d\'{e}duit l'\'{e}quation caract\'{e}ristique
de la matrice $A$:
$$
A^3-(k-1)A^2-(2k-1)A+k(k-1)=0.
$$
 
On sait bien que le spectre de la matrice associ\'{e}e d'un graphe
r\'{e}gulier connexe de degr\'{e} $k$ contient la valeur propre $k$
de multiplicit\'{e} 1.  Il doit y avoir donc encore deux valeurs
propres $\l_1$ et $\l_2$ de multiplicit\'{e} $m_1$ et $m_2$
satisfaisantes \`{a} l'\'{e}quation $A^2+A-(k-1)=0$.
\smallskip
 
{\bf Lemme 3.} $m_1=m_2$ implique $k=2$.
\smallskip
 
Ce lemme se d\'{e}montre facilement partant du syst\`{e}me
d'\'{e}quations
 
$$
\eqalign{
&m_1+m_2=k^2  \cr
&\l_1m_1+\l_2m_2=-k   \cr
&\l_1+\l_2=-1 }
$$
 
\noindent
Ici, la deuxi\`{e}me \'{e}quation veut dire que la somme de toutes les 
valeurs propres est \'{e}gale \`{a} la trace de la matrice.
 
Pour d\'{e}montrer le th\'{e}or\`{e}me, supposons que
$k\ne2$. On a alors $m_1\ne m_2$ et donc les racines $\l_1$ et
$\l_2$ sont des nombres rationnels: $\l_1=(-1+t)/2$, $\l_2=(-1-t)/2$
o\`{u} $t$ est un entier naturel v\'{e}rifiant \`{a} $4k-3=t^2$.
Du syst\`{e}me ci-dessus on d\'{e}duit maintenant l'\'{e}quation
$$
t^4-2t^2-16(m_1-m_2)t-15=0,
$$
donc $t$ doit \^{e}tre un diviseur du nombre 15.
 
Prenant successivement $t=1, 3, 5, 15$, on obtient
les valeurs $k=1, 3, 7, 57$, ce qu'il fallait d\'{e}montrer.
\smallskip
 
{\sl Remarque.} Cette d\'emonstration
a \'{e}t\'{e} invent\'{e}e par S.~Chmutov en 1990 au cours
d'un s\'{e}minaire dirig\'{e} par le pr\'{e}sent auteur.
Elle est beaucoup plus courte et claire que la d\'{e}monstration
donn\'{e}e dans [2].
\smallskip

{\sl Exercise 1.}
Construire le graphe de Moore de degr\'{e} 3.
\smallskip

{\sl Exercise 2.}
D\'{e}montrer que le graphe de Moore de degr\'{e} 4 n'existe pas
en calculant le nombre de 5--circuits qui passent par un sommet
fix\'{e} dans le graphe eventuel.


\beginsection Rev\^{e}tements des graphes.

\indent
{\bf Definition.}
Un rev\^{e}tement du graphe $G$ est un graphe $H$ avec une application
surjective des ensembles de sommets $p:V(H)\rightarrow V(G)$
v\'{e}rifiante les deux propri\'{e}t\'{e}s:
 
1. pour tout sommet $v\in V(G)$ l'image inverse $F_v=p^{-1}(v)$
forme un sous-graphe de $H$ sans ar\^{e}tes de la
cardinalit\'{e} constante $m$.
 
2. toute ar\^{e}te de $G$ dont les bouts sont $u$ et $v$
correspond \`{a} une famille de $m$ ar\^{e}tes de $H$ qui
joignent un \`{a} un les points du fibr\'{e} $F_u$ aux points
du fibr\'{e} $F_v$.
\smallskip
 
Si $H$ est un rev\^{e}tement de $G$, alors tout chemin $c$ dans
$G$ se l\`{e}ve uniquement \`{a} un chemin dans $H$.
En particulier, pour tout fibr\'{e} $F_v=p^{-1}(v)$, on peut
d\'{e}finir le groupe de monodromie $M(v) \subset \Perm(F_v)$
engendr\'{e} par les permutations provenantes des chemins
ferm\'{e}s dans $G$.
 
Par example, le graphe complet de 3 sommets $K_3$ poss\`{e}de
deux rev\^{e}tements divers de multiplicit\'{e} 2:
 
(1) la r\'{e}union disjointe de deux
exemplaires de $K_3$ avec la monodromie triviale;
 
(2) le circuit $C_6$ de 6 sommets avec la monodromie compl\`{e}te.
 
Soit $G$ un graphe r\'{e}gulier de degr\'{e} $k$ avec $k^2+1$ sommets
et $G'$ son sous-graphe
qu'on obtient en jetant de c\^{o}t\'{e} un sommet quelconque $v$ de
$G$ et tous ses voisins. L'ordre de $G'$ est donc $k(k-1)$ et il y a
une projection naturelle $p$ de cet ensemble de $k(k-1)$ points
sur l'ensemble de $k$ points voisins de $v$.
\smallskip
 
{\bf Proposition 2.}
{\sl Le graphe $G$ est un graphe de Moore si et seulement si
l'application $p$ est un rev\^{e}tement du graphe complet de l'ordre
$k$, dont la monodromie au-dessus des 3- et 4-cycles n'a pas
de points fixes.}
\smallskip
 
{\sl Exemple 1.}
Pour $k=3$, prenant le rev\^{e}tement double non-trivial du graphe
complet $K_3$ et y ajoutant les 4 sommets de la mani\`{e}re
standarde, on arrive au graphe de Petersen.
\smallskip
 
{\sl Exemple 2.}
Pour d\'{e}montrer l'existence du graphe de Moore de degr\'{e} $k=7$,
on doit construire un rev\^{e}tement 6-uple du graphe complet sur
7 sommets dont la monodromie satisfait aux exigences de la proposition 2.
Un tel rev\^{e}tement a \'{e}t\'{e} d\'{e}couvert par Irina Ignatovich
(Program Systems Institute, Pereslavl-Zalessky) en 1990 en utilisant
l'ordinateur. Apr\`{e}s cela, on a trouv\'{e} que le graphe de Moore
construit de cette mani\`{e}re existait dans la litt\'{e}rature depuis 1960
(voir [1]).
\smallskip
 
La monodromie du rev\^{e}tement de Ignatovich poss\`{e}de des
propri\'{e}t\'{e}s tout \`{a} fait exceptionnelles que nous d\'{e}crivons
dans la proposition suivante.
\smallskip
 
{\bf Proposition 3.}
{\sl Pour tout circuit $\gamma$ dans $K_7$ du longueur $r=2,3,4,5,6,7$
la monodromie de ce rev\^{e}tement au-dessus de $\gamma$ est une permutation
du fibr\'{e} d'ordre $r-1$. Plus pr\'{e}cisement, ces permutations ont
toujours la structure cyclique suivante: $(1,1,1,1,1,1)$, $(2,2,2)$, $(3,3)$,
$(4,1,1)$, $(5,1)$, $(3,2,1)$.}
 
\beginsection Autres constructions du graphe de Hoffman--Singleton.
 
\indent
{\bf 1.} La construction la plus classique du graphe de Hoffman--Singleton
est {\it le fibr\'{e} de Petersen au-dessus du graphe biparti $K_{5,5}$}.
Expliquons-nous.
 
Le graphe de Petersen $P_{10}$ peut \^{e}tre repr\'{e}sent\'{e} comme
deux circuits pentagonaux r\'{e}unis par cinq ar\^{e}tes selon
la formule $x \mapsto 2x \mod 5$ si les \'{e}l\'{e}ments de chaque
circuit sont d\'{e}nombr\'{e}s par les r\'{e}sidus modulo 5.
Actuellement, le d\'{e}nombrement \'{e}tant fix\'{e},
on peut choisir n'importe quelle des 10 applications
$x \mapsto \pm 2x+a \mod 5$ o\`{u} $a=0,1,2,3,4$.
On app\`{e}le une telle application {\it la torsion de Petersen\/}.
 
Un fibr\'{e} de Petersen au-dessus d'un graphe donn\'{e} $G$
est un graphe plus grand $H$ qui s'obtient de $G$ en rempla\c{c}ant
chaque sommet de $G$ par un curcuit pentagonal et chaque ar\^{e}te
de $G$ par une torsion de Petersen joignante ces deux circuits.
 
Maintenant, prenons le graphe complet biparti $K_{5,5}$
(``5 maisons et 5 puits'') comme la base de ``l'espace fibr\'{e}'',
suspendons un 5-circuit au-dessus du chaque sommet, soit maison ou puits,
et joignons la maison num\'{e}ro $i$ au puits num\'{e}ro $j$ par la
torsion de Petersen $x \mapsto 2x+ij \mod 5$.
\smallskip
 
{\sl Exercise 3.}
V\'{e}rifier que cette construction am\`{e}ne \`{a} un graphe de
diam\`{e}tre 2.
\medskip
 
{\bf 2.} Construction g\'{e}om\'{e}trique de J.~Seidel.
 
Soit $P$ l'ensemble des points et $L$ l'ensemble des lignes
dans l'espace projectif \`{a} 3 dimensions sur le corps fini de
2 \'{e}l\'{e}ments $F_2$. On a $\sharp(P)=15$, $\sharp(L)=35$.
On pose $V=P\cup L$ et l'on consid\`{e}re $V$ comme l'ensemble
des sommets du graphe de Hoffman--Singleton.
Un sommet $p\in P$ est uni par les ar\^{e}tes \`{a} tous les
sommets $l\in L$ correspondants aux lignes qui contiennent $p$.
Deux sommets $p_1,p_2\in P$ ne sont jamais uni.
Pour d\'{e}finir les ar\^{e}tes joignantes les sommets du type
ligne $l_1,l_2\in L$, on construit pr\'{e}alablement une
correspondance bijective entre l'ensemble $L$ et l'ensemble des triples
d'un ensemble auxiliaire $M$ de cardinalit\'{e} 7 ainsi que
les deux lignes se rencontrent si et seulement si les deux triple
correspondants ont exactement un point commun.
Alors, on joind les deux sommets $l_1,l_2\in L$ si et
seulement si les triples correspondants sont disjoints dans $M$.
\smallskip
 
{\sl Exercise 4.}
Trouver explicitement la correspondance d\'{e}crite ci-dessus
et v\'{e}rifier que le graphe ainsi obtenu est un graphe de Moore.
\medskip
 
{\bf Probl\`{e}me ouvert.}
Construire le graphe de Moore de degr\'{e} 57 ou d\'{e}montrer
qu'il n'existe pas.
 
\beginsection R\'{e}f\'{e}rences
 
\indent
[1] A.~J.~Hoffman, R.~R.~Singleton. On Moore graphs with diameters
2 and 3. -- IBM J. Res. Develop., 1960, 4, 497--504.
 
[2] E.~Bannai, T.~Ito. Algebraic combinatorics I. Association schemes.
Benjamin and Cummings, 1984.
 
[3] Ch.~Delorme, F.~Comellas. Table de grands graphes de degr\'{e} 
et diam\`{e}tre donn\'{e}s. -- 
{\tt http://maite71.upc.es/grup\_de\_grafs/table\_g.html}.

[4] S.~Abramov, S.~Chmutov, S.~Duzhin, I.~Ignatovich, A.~Nemytykh.
Quelques r\'{e}sultats sur le probl\`{e}me des grands graphes.
Manuscript (en Russe), 1991.
 
\end
