Devoir Maison 2018 – Coloration de graphes

Ce devoir est à réaliser dans un notebook Jupyter/SageMath. Utilisez les cellules ordinaires pour faire les calculs, et les cellules de texte (Markdown) pour ajouter vos commentaires et les réponses aux questions. Rappel : vous pouvez saisir des formules au format LaTeX entre les symboles $ (dollar).

Envoyez votre travail complet par mail. Vous pouvez soit l’exporter au format .ipynb (« File → Download as → Notebook (.ipynb) »), soit donner le lien du notebook sur https://jupyter.ens.uvsq.fr/ (et uniquement sur ce serveur).

Le but de ce sujet est de montrer comment on peut réduire certains problèmes sur les graphes à un calcul de bases de Gröbner. Il a été inspiré par ce cours de D. A. Cox.

Racines de l’unité

Factoriser avec Sage le polynôme $x^{15}-1$ .
Factoriser avec Sage le polynôme $x^{15}-y^{15}$ .
Soit $n$ un entier, caractériser la factorisation de $x^n-y^n$ en fonction de $n$ .
Calculer la base de Gröbner pour l’ordre lex de l’idéal
$〈 xyzt+1,\; xyz+xyt+xzt+yzt,\; xy+xz+xt+yz+yt+zt,\; x+y+z+t 〉.$
Quelle est la dimension de l’idéal ? Décrire sa variété.

Soient $n$ et $i$ deux entiers positifs, on définit les polynômes de $ℚ[x_1,\ldots,x_n]$

$e_i(x_1,\ldots,x_n) = \sum_{1 ≤ j_1 < \cdots < j_i ≤ n} \;\prod_{k=1}^i x_{j_k}$

$h_i(x_1,\ldots,x_n) = \sum_{j_1+\cdots+j_n=i} \;\prod_{k=1}^n x_k^{j_k}.$

Ainsi, par exemple

$\begin{aligned} e_1(x,y,z,t) &= h_1(x,y,z,t) = x + y + z + t,\\ e_2(x,y,z,t) &= xy + xz + xt + yz + yt + zt,\\ h_2(y,z,t) &= y^2 + yz + yt + z^2 + zt + t^2,\\ &\vdots\\ e_4(x,y,z,t) &= xyzt,\\ h_4(t) &= t^4. \end{aligned}$

Soit $n$ un entier, prouver que l’idéal de $ℚ[x_1,\ldots,x_n]$ défini par
$I = \bigl〈 \{e_i(x_1,\ldots,x_n)\}_{1 ≤ i < n} ∪ \{e_n(x_1,\ldots,x_n) + (-1)^n\} \bigr〉$
contient les polynômes $x_i^n-1$ pour tout $i$ .

Idéal de coloration

Un graphe non-orienté est dit $k$ -colorable lorsque on peut colorer ses sommets avec $k$ couleurs en sorte que deux sommets adjacents n’aient pas la même couleur. Voici un exemple de 3-coloration du graphe de Petersen.

Les problèmes de $k$ -coloration peuvent être résolus à l’aide des bases de Gröbner. Étant donné un graphe $G$ à $n$ sommets, on définit l’anneau de polynômes $ℚ[x_1,\ldots,x_n]$ , et l’idéal $I$ engendré par les polynômes

$x_i^k-1$ pour tout sommet $i$ , et
$h_{k-1}(x_i, x_j)$ s’il existe une arrête entre le sommet $i$ et le sommet $j$ .

Prouver qu’à chaque point de la variété de $I$ correspond une $k$ -coloration du graphe $G$ .
À l’aide d’une base de Gröbner, donner une 3-coloration du graphe ci-dessous.
Prouver que le graphe ci-dessous ne peut pas être 3-colorié.

Note: le dessin change de forme à chaque rechargement de la page, mais il s’agit toujours du même graphe. Pour vous simplifier la vie, voici sa matrice d’adjacence.

SageMath fournit une bibliothèque assez complète de théorie des graphes. Tous les graphes remarquables implantés sont disponibles dans l’espace de noms graphs.. Ainsi, pour créer le graphe de Petersen, on tapera la commande

G = graphs.PetersenGraph()

Tout graphe dans Sagemath a une méthode .vertices() qui renvoie la liste des sommets, et une méthode edges() qui renvoie la liste des arrêtes (une liste de triplets, dont vous pouvez ignorer le dernier élément) :

sage: G.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: G.edges()
[(0, 1, None),
 (0, 4, None),
 (0, 5, None),
 (1, 2, None),
 (1, 6, None),
 (2, 3, None),
 (2, 7, None),
 (3, 4, None),
 (3, 8, None),
 (4, 9, None),
 (5, 7, None),
 (5, 8, None),
 (6, 8, None),
 (6, 9, None),
 (7, 9, None)]

Écrivez une fonction coloration(G, k) qui prend en entrée un graphe $G$ et un entier $k$ et qui renvoie, si possible, une $k$ -coloration de $G$ par la méthode décrite précédemment.

Note : Pour créer un anneau avec un nombre arbitraire de variables vous pouvez utiliser la syntaxe
```
PolynomialRing(k, 'x', 10)
```

Coloration unique et Sudoku

On dit qu’un graphe est uniquement $k$ -colorable s’il a une unique $k$ -coloration à permutation des couleurs près. Par exemple, le graphe complet à $n$ sommets est uniquement $n$ -colorable.

Hillar et Windfeldt ont donné un critère pour détecter qu’un graphe est uniquement $k$ -colorable. Supposons que $G$ soit $k$ -colorable, et réordonnons ses sommets en sorte que les $k$ derniers sommets aient $k$ couleurs différentes. Renommons les variables

$x_1 > \ldots > x_{n-k} > y_1 > \ldots > y_k.$

Le graphe $G$ est uniquement $k$ -colorable si et seulement si son idéal de coloration contient les polynômes

$y_k^k - 1$ ,
$h_i(y_i,\ldots,y_k)$ pour $1 ≤ i < k$ ,
$x_i - y_j$ si la couleur de $i$ est égale à la couleur de $j$ .

Le graphe ci-dessous est-il uniquement 3-colorable ? Quel est son plus grand sous-graphe uniquement 3-colorable ?

On peut appliquer ce théorème à la solution des grilles de Sudoku. Soit $n$ un carré, un jeu de Sudoku d’ordre $n$ est une grille $n × n$ dont les cases sont vides, ou bien contiennent des entiers entre $1$ et $n$ . La grille de Sudoku est elle même divisée en $\sqrt{n}$ sous-grilles $\sqrt{n}×\sqrt{n}$ qui la recouvrent entièrement. Voici un exemple de Sudoku d’ordre 2.

1	2
			2
2		4
	1		3

Une grille de Sudoku d’ordre $n$ est dite soluble s’il est possible de remplir toutes les cases vides avec des entiers entre $1$ et $n$ en sorte que

sur chaque ligne apparaissent tous les entiers entre $1$ et $n$ ,
sur chaque colonne apparaissent tous les entiers entre $1$ et $n$ , et
dans chaque sous-grille apparaissent tous les entiers entre $1$ et $n$ .

Une grille soluble est dite soluble uniquement s’il existe une seule façon de remplir ses cases.

Expliquer comment ramener la solution d’une grille de Sudoku d’ordre $n$ à un problème de $n$ -coloration d’un graphe à $n^2$ sommets.

À l’aide d’un calcul de base de Gröbner, donner une solution à la grille

1	2
			2
2		4
	1		3

La solution est-elle unique ?

Note : des calculs de bases de Gröbner à 16 variables peuvent être assez coûteux. Si vous êtes amenés à interrompre un calcul de bases de Gröbner (par le bouton/menu « Interrupt kernel » de Jupyter, ou en tapant Ctrl+C dans le terminal), Sage risque de se retrouver dans un état inconsistant, et les calculs successifs de bases de Gröbner risquent de donner des résultats faux. Dans ce cas, on vous conseille de redémarrer le noyau Sage en utilisant le bouton/menu « Restart kernel » de Jupyter, ou bien en redémarrant Sage dans le terminal.

À l’aide d’un calcul de base de Gröbner, donner une solution à la grille

	2
			2
2		4
	1		3

La solution est-elle unique ?

À l’aide d’un calcul de base de Gröbner, donner une solution à la grille

8		9		3	2	5	4
2	1		4		5	8	7
	4	6		9	8		1	3
6	5		8	1		3		4
3		4		7	6	9	8
	8	1	2	4			5	7
4	3		6				9	2
	9	2	3		4	7		8
7	6			2	1	4	3

La solution est-elle unique ?

Note : bien que la solution de cette grille ne soit pas difficile, les calculs de bases de Gröbner commencent à bien peiner sur les problèmes de cette taille¹. Pour mettre toutes les chances de votre côté, n’oubliez pas que :

Il est beaucoup plus rapide de calculer la base de Gröbner d’une liste de générateurs déjà (presque) réduits, que d’une liste de générateurs quelconques. Utilisez les questions précédentes pour ajouter des polynômes déjà réduits à votre idéal de coloration.
Il est en général beaucoup plus facile de réduire pour l’ordre degrevlex, et ensuite faire un changement de base, que de réduire directement pour l’ordre lex (voir aussi le DM sur les changements d’ordre).
L’un des problèmes des algorithmes de calcul de bases de Gröbner sur $ℚ$ est l’explosion des coefficients des calculs intermédiaires. Ce problème disparaît en faisant les calculs sur un corps fini bien choisi…

Avec beaucoup de persévérance et d’optimisations, j’ai pu faire passer ce calcul en moins de 2 minutes. Saurez-vous faire mieux ?

À l’aide d’un calcul de base de Gröbner, armez-vous de patience et donnez une solution à la grille

8		9		3	2		4
2	1		4		5	8	7
	4	6		9	8		1	3
6	5		8			3		4
3		4		7	6	9	8
	8	1	2	4			5	7
4	3		6				9	2
	9	2	3		4	7		8
7	6			2	1	4	3

Ce qui montre que les bases de Gröbner ne sont pas le bon outil pour résoudre les Sudokus, mais passons. ↩