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.