# 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.

## 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\}$.
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$
$(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}}$
$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\}$.