Théorème d'Hoffman-Singleton

Le théorème d'Hoffman-Singleton est un théorème de théorie des graphes, prouvé en 1960 par Alan Hoffman et Robert Singleton. Ce théorème établit que tout graphe de Moore de diamètre 2 ne peut avoir qu'un degré $d$ égal à 2, 3, 7 ou 57.

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources (juillet 2013).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Exemples de graphes de Moore

Le pentagone est un graphe de Moore à 5 sommets ( $d=2$ ).
Le graphe de Petersen est un graphe de Moore à 10 sommets ( $d=3$ ).
Le graphe de Hoffman-Singleton est un graphe de Moore à 50 sommets ( $d=7$ ).

L'existence d'un graphe de Moore de diamètre 2 de degré $d=57$ possédant 3250 sommets est encore un problème ouvert.

Formulation algébrique

Théorème — Soit $A\in \mathrm {M} _{n}(\mathbb {R} )$ une matrice symétrique à coefficients 0 ou 1 de trace nulle. S'il existe $d\geq 1$ vérifiant :

A^{2}+A-(d-1)I_{n}={\begin{pmatrix}1&...&1\\..&.&..\\1&...&1\end{pmatrix}}=J_{n}

alors $d\in \{1,2,3,7,57\}$ .

Démonstration

On va tout d'abord montrer que $n=d^{2}+1$ .

Comme $A$ est symétrique on a :

(A^{2})_{ij}=\sum _{k=0}^{n}A_{ik}A_{kj}=\sum _{k=0}^{n}A_{ik}A_{jk}

En particulier $(A^{2})_{ii}$ représente le nombre de 1 dans la i-ème ligne de $A$ . Ainsi en remplaçant dans l'équation on obtient :

(A^{2})_{ij}+A_{ii}-(d-1)=1

et donc

(A^{2})_{ii}=d

.

D'autre part on a aussi $A.{\begin{pmatrix}1\\1\\\vdots \\1\end{pmatrix}}=d{\begin{pmatrix}1\\1\\\vdots \\1\end{pmatrix}}$ . Ainsi en remplaçant à nouveau dans l'équation on obtient :

(d^{2}+d-(d-1)){\begin{pmatrix}1\\1\\\vdots \\1\end{pmatrix}}=n{\begin{pmatrix}1\\1\\\vdots \\1\end{pmatrix}}

et donc

d^{2}+1=n

.

Cherchons ensuite des contraintes sur les valeurs propres de la matrice $A$ .

Soit donc $\lambda$ une valeur propre de $A$ et $v$ un vecteur propre associé. On a donc aussi :

(\lambda ^{2}+\lambda -(d-1)).v=J_{n}.v

Et donc $\lambda ^{2}+\lambda -(d-1)$ est une valeur propre de la matrice $J_{n}$ associée à $v$ , or cette matrice a pour valeurs propres 0 (associée à un sous-espace propre de dimension $n-1$ ) et $n$ (associé à un sous-espace propre de dimension $1$ ) avec de plus $\operatorname {Ker} (J_{n}-nI_{n})=\operatorname {Vect} ({\begin{pmatrix}1\\1\\\vdots \\1\end{pmatrix}})$ .

Ainsi :

soit $v\in {\textrm {Ker}}(J_{n}-nI_{n})$ et alors $\lambda =d$ ;
soit $(\lambda ^{2}+\lambda -(d-1))=0$ et donc $\lambda \in \{\lambda _{1},\lambda _{2}\}$ avec : $\lambda _{1}={\frac {-1+{\sqrt {4d-3}}}{2}}\quad \lambda _{2}={\frac {-1-{\sqrt {4d-3}}}{2}}$ .

Donnons les valeurs possible pour d.

$A\in {\mathcal {S}}^{n}(\mathbb {R} )$ donc elle est diagonalisable avec comme valeurs propres $d,\lambda _{1},\lambda _{2}$ et des sous-espaces propres associés de dimensions $1,\alpha _{1},\alpha _{2}$ , et comme la trace de $A$ est nulle on a :

\left\{{\begin{matrix}1+\alpha _{1}+\alpha _{2}=n=d^{2}+1\\d+\alpha _{1}\lambda _{1}+\alpha _{2}\lambda _{2}=0.\end{matrix}}\right.

La seconde équation donne :

$-{\frac {\alpha _{1}+\alpha _{2}}{2}}+{\sqrt {4d-3}}{\frac {\alpha _{1}-\alpha _{2}}{2}}=-d$ donc d'après la première relation $-{\frac {d^{2}}{2}}+{\sqrt {4d-3}}{\frac {\alpha _{1}-\alpha _{2}}{2}}=-d$ ou encore ${\sqrt {4d-3}}(\alpha _{1}-\alpha _{2})=-d(d-2)$ .

Si $\alpha _{1}=\alpha _{2}$ alors $d=2$ .
Sinon, on doit avoir ${\sqrt {4d-3}}\in \mathbb {Q}$ donc $4d-3=k^{2}$ on a alors $k(\alpha _{1}-\alpha _{2})=d(d-2)$ donc $k$ divise $d(d-2)$ donc $k$ divise ${\frac {k^{2}+3}{4}}{\frac {k^{2}-5}{4}}$ donc en particulier $k$ divise 15 et donc $k\in \{1,3,5,15\}$ d'où $d\in \{1,2,3,7,57\}$ .