Dimension (théorie des graphes)

Pour démontrer qu'un espace à 4 dimensions suffit, comme dans le cas précédent, on utilise des cercles^[3].

Le premier cercle est dans le plan X,Y. Ses ${\displaystyle m}$ points ont pour coordonnées :

${\displaystyle \left({\frac {1}{\sqrt {2}}}\cos \alpha _{i},{\frac {1}{\sqrt {2}}}\sin \alpha _{i},0,0\right)}$

où les ${\displaystyle \alpha _{i}}$ sont des mesures d'angles distinctes. On peut par exemple prendre :

${\displaystyle \alpha _{i}=i\cdot {\frac {2\pi }{m}}}$

encore que rien n'oblige à les répartir aussi régulièrement sur le cercle.

Le second cercle est dans le plan Z,T. Ses ${\displaystyle n}$ points ont pour coordonnées :

${\displaystyle \left(0,0,{\frac {1}{\sqrt {2}}}\cos \beta _{j},{\frac {1}{\sqrt {2}}}\sin \beta _{j}\right)}$

où les ${\displaystyle \beta _{j}}$ sont aussi des mesures d'angles distinctes.

La distance ${\displaystyle d}$ entre n'importe quel point du premier cercle et n'importe quel point du second cercle vérifie :

${\displaystyle d^{2}={\frac {1}{2}}(\cos ^{2}\alpha _{i}+\sin ^{2}\alpha _{i})+{\frac {1}{2}}(\cos ^{2}\beta _{j}+\sin ^{2}\beta _{j})={\frac {1}{2}}+{\frac {1}{2}}=1}$

On a exhibé une représentation dans l'espace à 4 dimensions du graphe biparti ${\displaystyle K_{m,n}}$ avec des arêtes de longueur 1. La dimension de ce graphe est donc au maximum 4.

Démontrons par ailleurs que le sous-graphe ${\displaystyle K_{3,3}}$ n'admet pas de telle représentation en dimension 3.

Si une telle représentation existait, on y verrait trois points ${\displaystyle A_{1}}$, ${\displaystyle A_{2}}$ et ${\displaystyle A_{3}}$ reliés par des arêtes de longueur 1 à trois points ${\displaystyle B_{1}}$, ${\displaystyle B_{2}}$ et ${\displaystyle B_{3}}$. Si ${\displaystyle A_{1}}$, ${\displaystyle A_{2}}$ et ${\displaystyle A_{3}}$ ne sont pas alignés, ils définissent un plan ${\displaystyle P}$. ${\displaystyle B_{1}}$ étant équidistant de ${\displaystyle A_{1}}$ et de ${\displaystyle A_{2}}$, il est sur le plan médiateur du segment ${\displaystyle [A_{1}A_{2}]}$. Il est aussi sur les deux autres plans médiateurs du triangle ${\displaystyle A_{1}A_{2}A_{3}}$. L'intersection de ces trois plans est la droite ${\displaystyle D}$ passant par le centre du cercle circonscrit à ${\displaystyle A_{1}A_{2}A_{3}}$ et perpendiculaire à ${\displaystyle P}$. Il en va de même pour ${\displaystyle B_{2}}$ et ${\displaystyle B_{3}}$. Or, on ne peut pas avoir trois points distincts à même distance de ${\displaystyle A_{1}}$ et de ${\displaystyle A_{2}}$ sur une même droite ${\displaystyle D}$. On a donc une absurdité dans ce cas. D'autre part, si ${\displaystyle A_{1}}$, ${\displaystyle A_{2}}$ et ${\displaystyle A_{3}}$ sont alignés, ils sont à même distance de ${\displaystyle B_{1}}$, ce qui est tout aussi absurde puisqu'ils sont distincts.

La dimension de ${\displaystyle K_{m,n}}$ est supérieure ou égale à celle de ${\displaystyle K_{3,3}}$ et il n'existe pas de plongement de ${\displaystyle K_{3,3}}$ dans ${\displaystyle E^{3}}$ avec des arêtes de longueur 1 : la dimension de ${\displaystyle K_{m,n}}$ est donc au minimum 4.

La dimension de ${\displaystyle K_{m,n}}$, pour ${\displaystyle m\geq 3}$ et ${\displaystyle n\geq 3}$, est à la fois supérieure ou égale à 4 et inférieure ou égale à 4 : elle est donc exactement 4.

La démonstration reprend encore une fois le principe des cercles d'intersection vide deux à deux.

Notons ${\displaystyle n}$ le nombre chromatique de ${\displaystyle G}$ et considérons un repère orthonormal ${\displaystyle (O,{\vec {u}}_{1},{\vec {u}}_{2},{\vec {u}}_{3},{\vec {u}}_{4},\ldots ,{\vec {u}}_{2n-1},{\vec {u}}_{2n})}$ de l'espace affine euclidien ${\displaystyle E^{2n}}$ de dimension ${\displaystyle 2n}$. Considérons ensuite les ${\displaystyle n}$ cercles des plans ${\displaystyle (O,{\vec {u}}_{1},{\vec {u}}_{2})}$, ${\displaystyle (O,{\vec {u}}_{3},{\vec {u}}_{4}),\ldots ,(O,{\vec {u}}_{2n-1},{\vec {u}}_{2n})}$, de centre ${\displaystyle O}$ et de rayon ${\displaystyle {\frac {1}{\sqrt {2}}}}$. On représente les sommets de ${\displaystyle G}$ de même couleur par des points différents sur un même cercle.

Toutes les arêtes de ${\displaystyle G}$ relient des sommets de couleurs différentes, c'est le principe même de la coloration d'un graphe. Les arêtes de ${\displaystyle G}$ sont donc toutes représentées par des segments reliant des points de cercles différents. De plus, ces segments sont tous, comme dans la démonstration précédente, de longueur 1.

On a donc bien construit un plongement de ${\displaystyle G}$ dans un espace affine euclidien de dimension ${\displaystyle 2n}$ tel que toutes les arêtes soient de longueur 1. Rien ne garantit que ce soit la plus petite dimension possible, donc on sait seulement que ${\displaystyle dim\,G\leq 2\,n}$.