Le problème dont je vais parler (et qui n'est pas lié au théorème des quatre couleurs) est relativement célèbre, mais toujours étonnant quand on le rencontre pour la première fois. Il a à mes yeux deux qualités : il se prête à de nombreuses variantes (qu'on peut trouver plus ou moins intéressantes), et il permet de réfléchir à ce qui peut faire la difficulté d'un problème ouvert.
Nombre chromatique du plan
On considère le (très grand) graphe $G=G(\mathbb{R}^2,\{1\})$ dont les sommets sont les points de $\mathbb{R}^2$, et où deux sommets sont reliés par une arête si et seulement s'ils sont à distance $1$. Il s'agit donc d'un graphe indénombrable et de degré indénombrable.
Question : quel est le nombre chromatique $\chi(G)$ de $G$ ?
On demande donc quel est le plus petit entier $k$ pour lequel il existe une application $f:\mathbb{R}^2\to\{1,\dots,k\}$ telle que $f(x)\neq f(y)$ dès que $x$ et $y$ sont à distance $1$ l'un de l'autre. Deux bornes très simples ont été trouvées à peut près au moment où le problème est apparu.
Question : quel est le nombre chromatique $\chi(G)$ de $G$ ?
On demande donc quel est le plus petit entier $k$ pour lequel il existe une application $f:\mathbb{R}^2\to\{1,\dots,k\}$ telle que $f(x)\neq f(y)$ dès que $x$ et $y$ sont à distance $1$ l'un de l'autre. Deux bornes très simples ont été trouvées à peut près au moment où le problème est apparu.
D'une part, il n'est pas difficile de voir que $G$ contient un graphe de nombre chromatique $4$, donc $\chi(G)\ge 4$ (image de droite).
D'autre part, on peut considérer un pavage hexagonal régulier où chaque tuile est de diamètre légèrement inférieur à $1$, puis colorier les tuiles avec $7$ couleurs (en attribuant les points frontaliers arbitrairement à une des tuiles adjacentes) de sorte que deux tuiles de même couleur soient à distance strictement supérieure à $1$. Ainsi, l'application qui à chaque point associe la couleur de la tuile contenant ce point convient, et $\chi(G)\le 7$.
Ainsi, on sait que $\chi(G) \in \{4,5,6,7\}$; mais on ne sait essentiellement rien de plus ! En tout cas dans l'axiomatique ZFC...
D'autre part, on peut considérer un pavage hexagonal régulier où chaque tuile est de diamètre légèrement inférieur à $1$, puis colorier les tuiles avec $7$ couleurs (en attribuant les points frontaliers arbitrairement à une des tuiles adjacentes) de sorte que deux tuiles de même couleur soient à distance strictement supérieure à $1$. Ainsi, l'application qui à chaque point associe la couleur de la tuile contenant ce point convient, et $\chi(G)\le 7$.
Ainsi, on sait que $\chi(G) \in \{4,5,6,7\}$; mais on ne sait essentiellement rien de plus ! En tout cas dans l'axiomatique ZFC...
Liens avec la logique
Le seul résultat important sur cette version du problème est dû à Falconer (Journal of Combinatorial Theory A, 1981) : un coloriage mesurable (i.e. tel que l'application $f$ ci-dessus est Lebesgue-mesurable) nécessite au moins $5$ couleurs. Or, on peut ajouter aux axiomes de ZF la Lebesgue-mesurabilité de toutes les parties de $\mathbb{R}$ (donc de $\mathbb{R}^2$) sans ajouter de contradiction (Solovay Annals of Mathematics 1970) ; ainsi, dans l'axiomatique de Solovay on a $\chi(G)\ge 5$.
Contrairement à ce qu'on pourrait penser, ce résultat n'amène pas à conjecturer que $\chi(G)\ge 5$ dans ZFC : en effet Shelah et Soifer on montré (Journal of Combinatorial Theory A, 2003) que des problèmes proches ont des solutions radicalement différentes suivant l'axiomatique choisie. Cherchons le nombre chromatique du graphe $G(\mathbb{S}^1,\{d\})$ dont les sommets sont les points du cercle $\mathbb{S}^1$ (supposé de longueur $1$) et où deux points sont reliés s'ils sont à distance $d$, supposé être un irrationnel de $[0,1]$. Dans ZFC, on peut choisir un élément de chaque classe de $\mathbb{S}^1$ modulo $d$ (i.e. les classes de $\mathbb{R} / (\mathbb{Z}+d\mathbb{Z})$). Il est alors possible, pour chaque élément choisi, de le colorier en noir puis de colorier les autres représentants de la même classe dans le cercle alternativement en blanc et noir. On montre ainsi que $\chi(G(\mathbb{S}^1,\{d\})=2$ dans ZFC. Shelah et Soifer montrent que ce nombre est infini dans l'axiomatique de Solovay.
Contrairement à ce qu'on pourrait penser, ce résultat n'amène pas à conjecturer que $\chi(G)\ge 5$ dans ZFC : en effet Shelah et Soifer on montré (Journal of Combinatorial Theory A, 2003) que des problèmes proches ont des solutions radicalement différentes suivant l'axiomatique choisie. Cherchons le nombre chromatique du graphe $G(\mathbb{S}^1,\{d\})$ dont les sommets sont les points du cercle $\mathbb{S}^1$ (supposé de longueur $1$) et où deux points sont reliés s'ils sont à distance $d$, supposé être un irrationnel de $[0,1]$. Dans ZFC, on peut choisir un élément de chaque classe de $\mathbb{S}^1$ modulo $d$ (i.e. les classes de $\mathbb{R} / (\mathbb{Z}+d\mathbb{Z})$). Il est alors possible, pour chaque élément choisi, de le colorier en noir puis de colorier les autres représentants de la même classe dans le cercle alternativement en blanc et noir. On montre ainsi que $\chi(G(\mathbb{S}^1,\{d\})=2$ dans ZFC. Shelah et Soifer montrent que ce nombre est infini dans l'axiomatique de Solovay.
Quelques variantes
Comme les notations utilisées le laissent entendre, on peut largement généraliser le problème : pour tout espace métrique $X$ et toute partie $D$ de $\mathbb{R}_+$, on peut considérer le graphe $G(X,D)$ dont les sommets sont les éléments de $X$ et où deux sommets sont reliés par une arête si leur distance appartient à $D$. On peut alors poser la question de déterminer le nombre chromatique de ce graphe.
Une première variante consiste à garder $X=\mathbb{R}^2$ mais à prendre $D=[1,1+\varepsilon]$ ; pour un $\varepsilon$ assez petit, les arguments ci-dessus restent valables et on a $\chi(G(\mathbb{R}^2,[1,1+\varepsilon]\in\{4,5,6,7\}$. En deçà d'une certaine valeur (environ 1,017), bien que le graphe obtenu ait beaucoup plus d'arêtes que $G$, on ne sait rien dire de plus ; pour des valeurs plus élevées voir le travail d'Exoo (Discrete and Computational Geometry 2005). Les questions de déterminer la limite de ces nombres chromatiques quand $\varepsilon$ tend vers $0$, ou de déterminer si cette limite est égale à $\chi(G)$ sont ouvertes. Notez que fixer un petit $\varepsilon$ permet d'investiguer numériquement cette question, c'est une approche qui semblerait intéressante mais je n'ai pas connaissance qu'elle ait été poursuivie sérieusement.
La variante qui a été la plus considérée est celle où $D=\{1\}$ et $X=\mathbb{R}^n$ ; notamment, on se demande quelle est l'asymptotique quand $n\to\infty$. Une chose évidente est que le nombre chromatique est croissant avec $n$, par inclusion.
Considérons maintenant le cas où $X$ est le plan hyperbolique $\mathbb{H}^2$ et $D=\{d\}$ un singleton. Contrairement au cas euclidien, la valeur de $d$ importe puisque $\mathbb{H}^2$ n'admet pas d'homothétie. Il est possible d'adapter les bornes du cas classique (mais la borne supérieure dépend de $d$), mais on sait très peu de choses. En particulier, on ne sait pas si $\chi(G(\mathbb{H}^2,\{d\}))$ est monotone, s'il est borné... Ces questions ont été soulevée par Kahle sur MathOverflow.
J'ai considéré quelques variantes de ce problème, en particulier celles discutée ici, dans un article à paraître à Geombinatorics, qui pose beaucoup plus de questions qu'il n'y répond.
Une première variante consiste à garder $X=\mathbb{R}^2$ mais à prendre $D=[1,1+\varepsilon]$ ; pour un $\varepsilon$ assez petit, les arguments ci-dessus restent valables et on a $\chi(G(\mathbb{R}^2,[1,1+\varepsilon]\in\{4,5,6,7\}$. En deçà d'une certaine valeur (environ 1,017), bien que le graphe obtenu ait beaucoup plus d'arêtes que $G$, on ne sait rien dire de plus ; pour des valeurs plus élevées voir le travail d'Exoo (Discrete and Computational Geometry 2005). Les questions de déterminer la limite de ces nombres chromatiques quand $\varepsilon$ tend vers $0$, ou de déterminer si cette limite est égale à $\chi(G)$ sont ouvertes. Notez que fixer un petit $\varepsilon$ permet d'investiguer numériquement cette question, c'est une approche qui semblerait intéressante mais je n'ai pas connaissance qu'elle ait été poursuivie sérieusement.
La variante qui a été la plus considérée est celle où $D=\{1\}$ et $X=\mathbb{R}^n$ ; notamment, on se demande quelle est l'asymptotique quand $n\to\infty$. Une chose évidente est que le nombre chromatique est croissant avec $n$, par inclusion.
Considérons maintenant le cas où $X$ est le plan hyperbolique $\mathbb{H}^2$ et $D=\{d\}$ un singleton. Contrairement au cas euclidien, la valeur de $d$ importe puisque $\mathbb{H}^2$ n'admet pas d'homothétie. Il est possible d'adapter les bornes du cas classique (mais la borne supérieure dépend de $d$), mais on sait très peu de choses. En particulier, on ne sait pas si $\chi(G(\mathbb{H}^2,\{d\}))$ est monotone, s'il est borné... Ces questions ont été soulevée par Kahle sur MathOverflow.
J'ai considéré quelques variantes de ce problème, en particulier celles discutée ici, dans un article à paraître à Geombinatorics, qui pose beaucoup plus de questions qu'il n'y répond.
Pourquoi ce problème est-il dur ?
Pour finir, je voudrais expliquer pourquoi ce genre de problème (et la majorité des questions posées dans l'article mentionné ci-dessus) me semble vraisemblablement très difficile, au sens où je serais étonné qu'on y trouve une solution simple.
Le graphe $G$ et ses semblables sont construits à partir d'un objet géométrique, mais en oublie presque la totalité ($G$ ne conserve que la relation « être à distance $1$ ») ; et la question - déterminer le nombre chromatique - est, elle, de nature combinatoire. Ainsi, les outils géométriques n'apportent que peu d'information (la méthode de pavage fourni des bornes supérieures à première vue assez grossières), et les outils combinatoires peinent à exploiter les spécificités du graphe. Une autre façon de le dire est que la géométrie nous a permis de définir très économiquement un graphe extrêmement complexe. La formulation du problèmes est donc simple, mais le problème lui même est loin de l'être. D'un certain point de vue, beaucoup de grandes conjectures de la théorie des nombre qui s'énoncent simplement sont difficiles pour des raison proches : elle posent des questions additives sur des objets, les nombres premiers, définis de façon multiplicative.
Il est certainement possible de construire de nombreux problèmes difficiles sur ce modèle ; il me semble beaucoup plus difficile d'en trouver qui aient l'élégance du nombre chromatique du plan.
Le graphe $G$ et ses semblables sont construits à partir d'un objet géométrique, mais en oublie presque la totalité ($G$ ne conserve que la relation « être à distance $1$ ») ; et la question - déterminer le nombre chromatique - est, elle, de nature combinatoire. Ainsi, les outils géométriques n'apportent que peu d'information (la méthode de pavage fourni des bornes supérieures à première vue assez grossières), et les outils combinatoires peinent à exploiter les spécificités du graphe. Une autre façon de le dire est que la géométrie nous a permis de définir très économiquement un graphe extrêmement complexe. La formulation du problèmes est donc simple, mais le problème lui même est loin de l'être. D'un certain point de vue, beaucoup de grandes conjectures de la théorie des nombre qui s'énoncent simplement sont difficiles pour des raison proches : elle posent des questions additives sur des objets, les nombres premiers, définis de façon multiplicative.
Il est certainement possible de construire de nombreux problèmes difficiles sur ce modèle ; il me semble beaucoup plus difficile d'en trouver qui aient l'élégance du nombre chromatique du plan.