Complexité et graphes boréliens

La combinatoire descriptive est un nouveau domaine de recherches mathématiques très dynamique, avec de nombreuses applications et connections (voir par exemple [11], [12]). Dans cette courte note, nous donnons un aperçu de ce domaine au moyen de quelques résultats d'un article récent [1]. L'idée de base de la combinatoire descriptive est d'étudier les problèmes classiques de combinatoire dans une classe restreinte de structures, et les relations possibles entre ces structures. La complexité des objets et des relations entre ces objets doit être bornée en un certain sens.

On dispose en mathématiques de différentes notions de complexité qui définissent diverses branches de combinatoire descriptive. L'article [1] relève de la complexité borelienne des sous-ensembles d'un espace métrique complet séparable (donc d'un espace polonais) connue depuis la fin du dix-neuvième siècle (voir [2]). L'introduction de cette échelle de complexité était motivée par l'analyse, et elle apparut assez rapidement  comme le premier niveau de la hiérarchie projective ${\bf \Delta}^1_1, {\bf \Sigma}^1_1, {\bf \Pi}^1_1, {\bf \Delta}^1_2, {\bf \Sigma}^1_2, {\bf \Pi}^1_2,....$ des sous-ensembles des espaces polonais (voir par exemple [10]). Un sous-ensemble ${\bf \Sigma}^1_1$ d'un espace polonais $X$ est la projection d'un sous-ensemble fermé du produit de $X$ avec un autre espace polonais. Les sous-ensembles ${\bf \Pi}^1_1$ sont les complémentaires des sous-ensembles ${\bf \Sigma}^1_1$, et la classe ${\bf \Delta}^1_1$ (qui est en fait la classe des sous-ensembles boréliens de $X$) est formée des sous-ensembles de $X$ qui sont à la fois ${\bf \Sigma}^1_1$ et ${\bf \Pi}^1_1$. Plus généralement les sous-ensembles ${\bf \Sigma}^1_{n+1}$ de $X$ sont les projections des sous-ensembles ${\bf \Pi}^1_n$ du produit de $X$ avec un autre espace polonais, les ensembles ${\bf \Pi}^1_{n+1}$ sont les complémentaires des ensembles  ${\bf \Sigma}^1_{n+1}$, et  les ensembles ${\bf \Delta}^1_{n+1}$ sont ceux qui sont à la fois ${\bf \Sigma}^1_{n+1}$ et ${\bf \Pi}^1_{n+1}.$

Un graphe borélien est une  structure de la forme $\mathcal{G}=(X, E)$ où l'ensemble $X$ des sommets est un espace polonais, et l'ensemble $E$ des arêtes est un sous-ensemble borélien symétrique de $X^2\setminus \{(x,x): x\in X\}.$ Tout graphe fini est trivialement borélien mais la classe est bien sûr beaucoup plus vaste.  Un homomorphisme d'un graphe  $\mathcal{G}=(X, E)$ dans un graphe  $\mathcal{H}=(Y, F)$ est une application $f: X\rightarrow Y$ telle que
$$(x,y)\in E  \implies (f(x), f(y))\in F.$$
Nous écrivons alors $\mathcal{G}\leq\mathcal{H}$, et $\mathcal{G}<\mathcal{H}$ si $\mathcal{G}\leq\mathcal{H}$ mais $\mathcal{H}\nleq\mathcal{G}$. Cette terminologie se transfère naturellement à la classe des graphes boréliens. Plus precisément, si $\mathcal{G}=(X, E)$ et  $\mathcal{H}=(Y, F)$ sont des graphes boréliens, nous écrivons $\mathcal{G}\leq_B \mathcal{H}$ lorsqu'il existe une application borélienne $f: X\rightarrow Y$ qui est un homomorphisme de $\mathcal{G}$ dans $\mathcal{H}.$ L'étude des graphes boréliens et de leurs homomorphismes étend naturellement celle des graphes finis avec des homomorphismes arbitraires, mais elle donne naissance à des nouveaux phénomènes  qui ne se présentent pas dans le cadre classique.  Par exemple, un graphe borélien sans cycle $\mathcal{G}$ n'est pas nécessairement de nombre chromatique borélien 2, c'est-à-dire n'est pas nécessairement Borel bipartite (i.e., $\leq_B \mathcal{K}_2$).[*]

Un exemple particulièrement intéressant d'un tel graphe, important pour [1], est le graphe du shift $ \mathcal{S}=([\mathbb{N}]^\mathbb{N}, S)$ sur l'ensemble $[\mathbb{N}]^\mathbb{N}$ des sous-ensembles infinis de $\mathbb{N}$ engendré par la fonction
$$S(x)=x\setminus \{\min x\}.$$
C'est un graphe sans cycle et il admet donc un homomorphisme dans le graphe complet $\mathcal{K}_2$ à deux sommets, mais un résultat classique de la théorie de Ramsey [3] implique que $([\mathbb{N}]^\mathbb{N}, S)$ n'admet aucun homomorphisme borélien dans un graphe fini. Cependant, l'application $x\mapsto \min x$ est un homomorphisme borélien de  $([\mathbb{N}]^\mathbb{N}, S)$ dans le graphe complet $\mathcal{K}_\mathbb{N}$ sur l'ensemble $\mathbb{N}.$ Mais en fait, il existe des graphes boréliens sans cycle $\mathcal{G}$ qui n'admettent aucun homomorphisme borélien dans $\mathcal{K}_\mathbb{N}$. Un exemple typique d'un tel graphe est le graphe $\mathcal{G}_0=(2^\mathbb{N}, E_0)$ de [4] défini comme suit :
$$(x,y)\in E_0  \mbox { iff } (\exists n) [x|n=y|n=s_n \wedge x(n)\neq y(n) \wedge (\forall m>n) x(m)=y(m)],$$
où $s_n\in 2^n$ $(n\in \mathbb{N})$ est une suite avec la propriété: $(\forall t\in 2^{<\mathbb{N}}) (\exists n)~ t\subseteq s_n.$
Modulo la relation d'équivalence $\equiv_B$[**] le graphe $\mathcal{G}_0$ ne dépend pas du choix de la suite $s_n\in 2^n$ $(n\in \mathbb{N})$  dès lors que la condition de densité est satisfaite.  

Dans le cadre classique (voir [5]), pour un graphe fini donné $\mathcal{H},$ on étudie la complexité de la classe de graphes finis : $$\mathcal{H}^\perp=\{\mathcal{G}: \mathcal{G}\not\leq \mathcal{H}\}.$$

Un cas particulièrement intéressant est celui où $\mathcal{H}$ est un graphe complet. Par exemple, la célèbre conjecture de Hedetniemi ([6], [7]) concerne ce cas, et consiste à savoir si pour tout entier positif $n$ la classe $\mathcal{K}_n^\perp$ est stable par produits $\mathcal{G}\times \mathcal{H}$[***], ou de façon équivalente, est stable par l'infimum $\mathcal{G}\wedge \mathcal{H}$ relatif au quasi-ordre $\leq.$ La théorie classique énonce (voir [5]) que pour les graphes finis $\mathcal{H}$ où les boucles sont permises, le problème de l'appartenance à $\mathcal{H}^\perp$ est NP-complet ou peut être résolu par un algorithme en temps polynomial.  Un cas particulier où $\mathcal{H}^\perp $ est simple est s'il a une base finie, donc s'il existe un nombre fini $\mathcal{B}_1,...,\mathcal{B}_k$ d'éléments de  $\mathcal{H}^\perp$ tels que pour tout $\mathcal{G}\in \mathcal{H}^\perp$ il existe $1\leq i\leq k$ tel que $\mathcal{B}_i\leq \mathcal{G}.$ Lorsque $k=1,$ c'est-à-dire lorsque $\mathcal{H}^\perp $ a un élément minimal $\mathcal{B}_1$, alors l'ensemble $\mathcal{H}^\perp$ est clairement stable par produits. Notons aussi que dans ce cas la paire de graphes $(\mathcal{B}_1\times \mathcal{H}, \mathcal{B}_1)$ forme un gap, c'est-à-dire que  $\mathcal{B}_1\times \mathcal{H}<\mathcal{B}_1$ mais il n'y a pas de graphe $\mathcal{G}$ tel que $\mathcal{B}_1\times \mathcal{H}<\mathcal{G}<\mathcal{B}_1.$ Dans ce contexte, mentionnons un résultat assez ancien de [8] qui énonce que pour toute paire de graphes finis $(\mathcal{G}, \mathcal{H})$ tels que $\mathcal{G}<\mathcal{H}$ et $\mathcal{H}\not\leq \mathcal{K}_2$ il y a un graphe fini $\mathcal{I}$ tel que $\mathcal{G}<\mathcal{I}<\mathcal{H}.$ Autrement dit, la classe des graphes finis avec les homomorphismes généraux a seulement un gap, qui est $(\mathcal{K}_1, \mathcal{K}_2).$

Examinons maintenant le comportement des graphes et des homomorphismes boréliens vis-à-vis des questions de complexité de la version borelienne de l'orthogonal notée
$$\mathcal{K}_X^{\perp_B}=\{\mathcal{G}: \mathcal{G} \mbox{ borélien et }\mathcal{G}\not\leq_B \mathcal{K}_X\}$$
où $X$ est un espace polonais. Remarquons d'abord que les graphes boréliens complets $\mathcal{K}_X$ où $X$ est un espace polonais non dénombrable sont tous $\equiv_B$-équivalents. Comme $\mathcal{G}\leq_B\mathcal{K}_X$ pour tout graphe borélien  $\mathcal{G}=(X, E),$ on a $\mathcal{K}_X^{\perp_B}=\emptyset$ pour tout espace polonais non dénombrable $X.$ On a d'autre part $\mathcal{K}_X\equiv_B \mathcal{K}_\mathbb{N}$ pour tout espace polonais dénombrable infini $X$. Nous pouvons donc nous limiter aux ensembles  $\mathcal{K}_\mathbb{N}^{\perp_B}$ et $\mathcal{K}_n^{\perp_B}$ avec $n\geq 1$ entier.

Un résultat important de [4] connu sous le nom de {\it $\mathcal{G}_0$-dichotomy} énonce que le graphe $\mathcal{G}_0$ décrit ci-dessus est l'élément minimal de $\mathcal{K}_\mathbb{N}^{\perp_B}.$  Il s'ensuit que la version borélienne de la conjecture de Hedetniemi est vraie pour  $\mathcal{K}_\mathbb{N}^{\perp_B}$ (c'est-à-dire que cette classe est stable par produit)  et que $(\mathcal{G}_0\times \mathcal{K}_\mathbb{N}, \mathcal{G}_0)$ est un gap dans la classe des graphes et des homomorphismes boréliens. Un résultat similaire a été établi récemment dans [9], où l'existence d'un élément minimal $\mathcal{G}_{\rm odd}$ dans $\mathcal{K}_2^{\perp_B}$ a été montrée. Il s'ensuit que la classe $\mathcal{K}_2^{\perp_B}$ satisfait la version borélienne de la conjecture de Hedetniemi et que $(\mathcal{G}_{\rm odd}\times \mathcal{K}_2, \mathcal{G}_{\rm odd})$ est lui aussi un gap borélien. Il reste à examiner la complexité des classes $\mathcal{K}_n^{\perp_B}$ avec $n\geq 3$ ainsi que celle de leur intersection $\bigcap_{n=3}^\infty \mathcal{K}_n^{\perp_B}.$ C'est le propos du résultat principal de [1].

Avant d'énoncer ce résultat, rappelons que le graphe du shift $ \mathcal{S}=([\mathbb{N}]^\mathbb{N}, S)$ a été défini ci-dessus. Pour $V\subseteq [\mathbb{N}]^\mathbb{N}$, on note $\mathcal{S}|V$ le sous-graphe induit $(V, S).$ Le résultat principal de [1] énonce que l'ensemble

$$\{V\subseteq [\mathbb{N}]^\mathbb{N}: V \mbox{ fermé et }\mathcal{S}|V\leq_B \mathcal{K}_3\}$$
est ${\bf \Sigma}^1_2$-complet[****]. Un théorème général de [4] montre que cet ensemble est égal à

$$\{V\subseteq [\mathbb{N}]^\mathbb{N}: V \mbox{ fermé et } \mathcal{S}|V\leq_B \mathcal{K}_n\}$$
pour tout entier $n\geq 3.$ Puisque $\{V\subseteq [\mathbb{N}]^\mathbb{N}: V \mbox{ fermé }\}$ est un espace borélien standard, il s'ensuit que toutes les classes $\mathcal{K}_n^{\perp_B}$ où $n\geq 3$ de même que leur intersection $\bigcap_{n=3}^\infty \mathcal{K}_n^{\perp_B}$ sont de complexité élevée, et qu'en particulier aucune de ces classes n'admet une base finie ou dénombrable. En effet, si $\mathcal{B}_1,\mathcal{B}_2,..., \mathcal{B}_k,...$ était une suite de graphes boréliens formant une base de l'une des classes $\mathcal{K}_n^{\perp_B}$  $(n\geq 3)$ ou $\bigcap_{n=3}^\infty \mathcal{K}_n^{\perp_B},$ l'ensemble $\{V\subseteq [\mathbb{N}]^\mathbb{N}: V \mbox{ fermé et }\mathcal{S}|V\leq_B \mathcal{K}_3\}$ serait ${\bf \Pi}^1_2$ et donc ${\bf \Delta}^1_2$, ce qui contredirait le fait qu'un ensemble ${\bf \Sigma}^1_2$-complet n'est pas ${\bf \Delta}^1_2$ (voir [10]).

Concluons ce rapport en résumant les résultats principaux. Notons tout d'abord que $\mathcal{K}_2$ est minimal dans la classe  $\mathcal{K}_1^\perp$ des graphes finis  ainsi que dans la classe $\mathcal{K}^{\perp_B}$ des graphes boréliens. Ces deux classes sont stables par produit et elles satisfont donc la version correspondante de la conjecture de Hedetniemi. La paire $(\mathcal{K}_1, \mathcal{K}_2)$ est un gap dans la classe des graphes finis ainsi que dans celle des graphes boréliens. Le résultat de [8] montre que $(\mathcal{K}_1, \mathcal{K}_2)$ est le seul gap dans la classe des graphes finis, et nous avons vu ci-dessus qu'au-delà de $(\mathcal{K}_1, \mathcal{K}_2),$ la class des graphes boréliens pré-ordonnée par les homomorphismes boréliens a au moins deux autres gaps, $(\mathcal{G}_0\times \mathcal{K}_\mathbb{N}, \mathcal{G}_0)$  et $(\mathcal{G}_{\rm odd}\times \mathcal{K}_2, \mathcal{G}_{\rm odd}).$

Dans la classe des graphes finis, la conjecture de Hedetniemi a été vérifiée pour $\mathcal{K}_1^\perp,$ $\mathcal{K}_2^\perp$  et $\mathcal{K}_3^\perp$ (see [13]) mais elle a été réfutée pour $\mathcal{K}_n^\perp$ si $n\geq 5$ (voir [7], [14]). La version borélienne de la conjecture de Hedetniemi est vraie pour $\mathcal{K}_1^{\perp_B}$, $\mathcal{K}_2^{\perp_B}$ et $\mathcal{K}_\mathbb{N}^{\perp_B}$ et fausse pour  $\mathcal{K}_n^{\perp_B}$ si $n\geq 5$ puisque pour $n\geq 5$ elle est fausse pour les graphes finis. Cependant, le cas $\mathcal{K}_4^\perp$ of de la conjecture de Hedetniemi dans la classe des graphes finis, et les cas $\mathcal{K}_3^{\perp_B}$ et $\mathcal{K}_4^{\perp_B}$ de la version borélienne de la conjecture de Hedetniemi sont encore des problèmes ouverts.

NOTES :

[*] On note $\mathcal{K}_X$ le graphe complet $(X, X^2\setminus \{(x,x): x\in X\}$ sur l'ensemble de sommets $X$.

[**] $\mathcal{G}\equiv_B\mathcal{H}$ si et seulement si $\mathcal{G}\leq_B\mathcal{H} $ et $\mathcal{H}\leq_B \mathcal{G}.$

[***] Le produit $\mathcal{G}\times \mathcal{H}$ de deux graphes $\mathcal{G}=(X,E)$ et $\mathcal{H}=(Y,F)$ est le graphe dont l'ensemble des sommets est $X\times Y$ et dont l'ensemble des arêtes  $E\bigotimes F$ est constitué des paires $((x,y), (x',y'))$ telles que $(x,x')\in E$ et $(y, y')\in F.$ Notons que $\mathcal{G}\times \mathcal{H} \leq \mathcal{G}$ et $\mathcal{G}\times \mathcal{H}\leq \mathcal{H}$, et de plus que $\mathcal{B}\leq \mathcal{G}\times\mathcal{H}$ pour tout graphe $\mathcal{B}$ tel que $\mathcal{B}\leq \mathcal{G}$ et $\mathcal{B}\leq \mathcal{H}$ . En d'autres termes le produit  $\mathcal{G}\times \mathcal{H}$ est la borne inférieure $\mathcal{G}\wedge \mathcal{H}$ de $\mathcal{G}$ et $\mathcal{H.}$ C'est également vrai dans le cadre des graphes et des homomorphismes boréliens.

[****] Un sous-ensemble $A$ d'un espace polonais $X$ est {\it ${\bf \Sigma}^1_2$-complet} s'il est ${\bf \Sigma}^1_2$ et a la propriété que pour tout sous-ensemble ${\bf \Sigma}^1_2$ $B$ d'un espace polonais $Y$,  il existe une application borélienne $f:Y\rightarrow X$ telle que pour tout $y\in Y$, on a $y\in B \iff f(x)\in A.$