Théorème d'Hoffman-Singleton

Théorème d'Hoffman-Singleton: Le théorème d'Hoffman-Singleton établit en 1960 par Alan Hoffman (en) et Robert Singleton stipule que tout Graphe de Moore de diamètre 2 ne peut avoir qu'un degré d égal à 2,3,7 ou 57.

Sommaire

1 Les différents graphes de Moore

2 Formulation Algébrique

3 Voir aussi

3.1 Liens internes

3.2 Références

Les différents 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 possédant 57 sommets est encore un problème ouvert.

Formulation Algébrique

Théorème — Soit $A \in\mathcal{S}^n(\R)$ une matrice à coefficient 0 ou 1 de trace nulle tel qu'il existe $d \ge 1$ vérifiant:
$A^{2}+A-(d-1)I_{n}=\begin{pmatrix} 1 & ... & 1\\ .. & . & ..\\ 1& ... & 1\end{pmatrix}=J_{n}$
On a 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) i i$ représente le nombre de 1 dans la ième ligne de $A$ . Ainsi en remplaçant dans l'équation on obtient:
$(A 2) i j + A i i - (d - 1) = 1$ et donc $(A 2) i i = 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 $λ$ une valeur propre de $A$ et $v$ un vecteur propre associé. On a donc aussi :
$(λ 2 + λ - (d - 1)). v = J n . v$
Et donc $(λ 2 + λ - (d - 1))$ est une valeur propre de la matrice $J n$ associée à $v$ , or cette matrice à pour valeurs propres 0 (associée à un sous espace propre de dimension n-1) et n (associé à un sous espace propre de dimension un) avec de plus $\textrm{Ker}(J_{n}-nI_{n})=Vect(\begin{pmatrix}1 \\1\\ \vdots \\ 1 \end{pmatrix})$ .

Ainsi:

Soit $v \in \textrm{Ker}(J_{n}-nI_{n})$ et alors $λ = d$

Soit $(λ 2 + λ - (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(\R)$ donc elle est diagonalisable avec comme valeurs propres $d,λ 1,λ 2$ et des sous espaces propres associés de dimensions $1,α 1,α 2$ , 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 $α 1 = α 2$ alors d=2

Sinon on doit avoir $\sqrt{4d-3} \in \mathbb{Q}$ donc $4 d - 3 = k 2$ on a alors $k (α 1 - α 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\}$ .

Voir aussi

Liens internes

Théorie des graphes

Graphe régulier

Graphe de Moore

Références

Sujet ENS 1986 section A1 épreuve de MATH.2

Portail de l'informatique théorique

Catégorie :
Famille de graphes

Contenu soumis à la licence CC-BY-SA. Source : Article Théorème d'Hoffman-Singleton de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

Graphe de Moore — En théorie des graphes, un graphe de Moore est un graphe régulier dont le nombre de sommets, pour un degré et un diamètre donnés, est maximal. Les graphes de Moore ont été nommés par Alan Hoffman et Robert Singleton en 1960 en hommage à Edward F … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français

Mark and share
Search through all dictionaries
Translate…
Search Internet

Share the article and excerpts