Coloriages aléatoires

Université de Grenoble - Préparation à l’agrégation

Christophe Leuridan

Lorsqu’on colorie une carte du monde, on souhaite que deux pays ayant une frontière
commune soient de couleur différentes. Le théorème des quatre couleurs affirme que
quatre couleurs suffisent à colorier toute carte plane pourvu que les pays soient d’un
seul tenant.
Ce problème est un cas particulier du coloriage d’un graphe fini : il suffit d’associer un
sommet à chaque pays et de relier deux sommets par une arête si les pays correspondant
ont une frontière commune. Dans ce texte, nous étudions un algorithme pour simuler le
coloriage aléatoire d’un graphe.

1 Introduction : le polynôme chromatique

Un graphe fini non orienté G est la donnée d’un ensemble fini V et d’une partie E de
l’ensemble P2 (V) des parties de V à deux éléments. Les éléments de V sont les sommets
(en anglais « vertices ») et les éléments de E sont les arêtes (en anglais « edges »).
Si u et v sont deux sommets distincts, on dira que u et v sont voisins dans G et on
notera u ∼G v lorsque {u, v} ∈ E. On appellera degré d’un sommet v dans le graphe G,
noté dv , le nombre de voisins de v dans G. On notera ∆ le degré maximum.
On se donne un ensemble fini C de couleurs. Un coloriage admissible de G par C est
une application x de V dans C telle que pour tout u, v ∈ V, u ∼ G v entraı̂ne x(u) 6=
x(v). On notera A(G, C) l’ensemble des coloriages admissibles de G par C. Dénombrer
le nombre d’éléments de A(G, C) est souvent difficile, en dehors de quelques graphes
particulièrement simples. On dispose toutefois d’un résultat théorique remarquable.

Théorème 1 Soit G un graphe fini non orienté. Il existe un unique polynôme P G appelé
polynôme chromatique tel que pour tout ensemble fini C de couleurs,

#A(G, C) = PG (#C).

De plus, PG (q) > 0 dès que q ≥ ∆ + 1 et PG (q) ∼ q #V quand q → +∞.

L’existence du polynôme chromatique se montre par récurrence sur le nombre d’arêtes

du graphe G. Etant donné une arête e d’un graphe G reliant les sommets v 1 et v2 , on
peut considérer le graphe G \ e obtenu en supprimant l’arête e et le graphe G/e obtenu
en contractant l’arête e : les deux sommets v 1 et v2 sont remplacés par un seul sommet
v dans le graphe G, et les voisins de v dans G/e sont les voisins de v 1 ou de v2 dans G
autres que v1 et v2 . Les graphes G \ e et G/e possèdent moins d’arêtes que G et on vérifie
facilement que PG (q) = PG\e (q) − PG/e (q).

1
 Suggestions de développement :
1. Compléter la démonstration du théorème 1.
2. Montrer que PG (∆) peut être nul.
3. Calculer PG (n) pour le graphe complet à N sommets, défini par V = [1 . . . N ] et
E = P2 (V). Comment simuler un coloriage aléatoire de ce graphe ?
4. Calculer PG (n) pour le graphe défini par V = [1 . . . N ] et E = {{k, k + 1}; k ∈
[1 . . . N − 1]}. Comment simuler un coloriage aléatoire de ce graphe ?
5. Calculer PG (n) pour le graphe défini par V = [1 . . . N ] et E = {{k, k + 1}; k ∈
[1 . . . N − 1]} ∪ {1, n}.

2 Une chaı̂ne de Markov sur les coloriages

On fixe désormais le graphe G et l’ensemble C des couleurs. Comme l’ensemble A =

A(G, C) de tous les coloriages admissibles est souvent difficile à décrire et à dénombrer,
il est difficile de simuler directement la loi uniforme sur A. Une idée est de simuler une
chaı̂ne de Markov sur l’ensemble C V des coloriages (admissibles ou non) dont la mesure
invariante est la loi uniforme sur A.
On construit par récurrence une chaı̂ne de Markov (X n )n∈N de la façon suivante.
On part d’un coloriage X0 ∈ C V . Pour passer du coloriage Xn au coloriage Xn+1 ,
– on choisit au hasard un sommet Vn+1 ;
– on choisit au hasard une couleur Cn+1 ;
– si tous les voisins de Vn+1 ont une couleur différente de Cn+1 , on change la couleur
de Vn+1 en Cn+1 .
Par conséquent, le coloriage Xn+1 diffère du coloriage Xn en au plus un point, Vn+1 , et
Xn+1 (Vn+1 ) = Cn+1 si Xn (u) 6= Cn+1 pour tout u voisin de Vn+1 . Sinon, Xn+1 = Xn .
Les probabilités de transition sont simples à décrire : si un coloriage y diffère de x en
un seul sommet v et si y(u) 6= y(v) pour tout voisin u de v, alors p(x, y) = (#V#C) −1 .
Les autres probabilités de transition sont nulles à l’exception des probabilités p(x, x).
On vérifie facilement que si A 6= ∅, la loi uniforme sur A est une probabilité invariante
de la chaı̂ne de Markov (Xn )n∈N .
L’ensemble des coloriages admissibles possède des propriétés remarquables pour cette
chaı̂ne de Markov.

Proposition 2 (Propriétés de la partie A)

1. La partie A est absorbante : si X0 ∈ A, alors Xn ∈ A pour tout n ∈ N.
2. Si #C ≥ ∆ + 1, alors la partie A est accessible depuis tout état de C V .
3. Si #C ≥ ∆ + 2, alors tout état de A est accessible depuis tout état de C V .

Donnons une idée de la démonstration du point 3, le plus délicat. Pour passer d’un
état x ∈ A, à un état y ∈ A autre que x, on choisit un sommet v 1 où les deux coloriages
diffèrent. Notons N (v1 ) (comme « neighbourhood ») l’ensemble des voisins de v 1 . Si
x(u) 6= y(v1 ) pour tout u ∈ N (v1 ), on peut directement changer la couleur de v 1 en y(v1 ).
Sinon, il faut au préalable changer les couleurs des voisins u de v 1 tels que x(u) = y(v1 ).
Le fait que #C ≥ ∆ + 2 permet de remplacer ces couleurs une à une par une couleur
différente de y(v1 ). Comme cette opération ne modifie pas les couleurs des sommets où
x et y coı̈ncident, elle aboutit à un coloriage plus proche de y.

2
 De ces propriétés, on déduit facilement le résultat suivant.

Théorème 3 Si #C ≥ ∆ + 2, la loi de Xn tend vers la loi uniforme sur A.

Suggestions de développement :
1. Pourquoi la suite (Xn )n∈N est-elle une chaı̂ne de Markov ?
2. Justifier et compléter le calcul des probabilités de transition.
3. Montrer que la loi uniforme sur A est une probabilité invariante. Est-ce la seule ?
4. Justifier les résultats concernant la partie A. Montrer si #C = ∆ + 1, tous les états
de A ne communiquent pas nécessairement entre eux.
5. Que peut-on en déduire sur la nature des états (récurrence, transience) et le com-
portement asymptotique de la suite (X n )n∈N ?
6. Justifier la convergence en loi. Que sait-on sur la vitesse de convergence ?
7. Simuler la chaı̂ne de Markov sur un graphe simple.

3 Un couplage

Dans ce paragraphe, on se propose d’étudier l’influence des conditions initiales sur

la chaı̂ne de Markov. Pour cela on se donne des variables aléatoires indépendantes X 0 et
Y0 à valeurs dans C V , V1 , V2 , . . . de loi uniforme sur V et C1 , C2 , . . . de loi uniforme sur C
et on définit les chaı̂nes de Markov (X n )n∈N et (Yn )n∈N par les relations de récurrence
Xn+1 = f (Xn , Vn+1 , Cn+1 ) et Yn+1 = f (Yn , Vn+1 , Cn+1 ), en notant f (x, v, c) le coloriage
obtenu à partir de x en changeant la couleur de v en c si les voisins de v ont une couleur
différente de c.
On définit la distance de Hamming entre deux coloriages x et y en notant d(x, y)
le nombre de sommets où les coloriages x et y diffèrent. Pour tout n ∈ N, notons
Dn = d(Xn , Yn ) et Fn = σ(X0 , Y0 , . . . , Xn , Yn ). Nous allons étudier le comportement de
la suite (Dn )n∈N .

Théorème 4 Pour tout n ∈ N,

 (3∆ − #C) 
E[Dn+1 |Fn ] ≤ 1 + Dn .
#V#C

Par conséquent, si #C ≥ 3∆, (Dn )n∈N est une surmartingale positive, qui converge
presque sûrement vers 0.

Démonstration. Démontrons l’inégalité du théorème. Il s’agit de montrer que quels que

soient les coloriages x et y,

  (3∆ − #C) 
E d f (x, Vn+1 , Cn+1 ), f (y, Vn+1 , Cn+1 ) ≤ 1 + d(x, y). (1)
#V#C

Soit l = d(x, y). Choisissons un chemin x = x 0 , . . . , xl = y de longueur minimale joignant

x à y : pour tout k ∈ [1 . . . l], les coloriages x k−1 et xk différent en un seul sommet.
Pour montrer l’inégalité (1), il suffit de montrer l’inégalité analogue pour chaque couple
(xk−1 , xk ). Il suffit donc de montrer l’inégalité (1) dans le cas particulier où d(x, y) = 1.

3
 Supposons donc que d(x, y) = 1 et notons v l’unique sommet où les coloriages x et
y diffèrent.
La transformation f (·, Vn+1 , Cn+1 ) modifie chaque coloriage x et y en au plus un
sommet, Vn+1 , dont la couleur devient alors Cn+1 . La distance entre les coloriages
f (x, Vn+1 , Cn+1 ) et f (y, Vn+1 , Cn+1 ) ne peut donc valoir que 0, 1 ou 2.
Pour que d(f (x, Vn+1 , Cn+1 ), f (y, Vn+1 , Cn+1 )) = 2, il faut qu’un seul des coloriages
x et y soit modifié. Cela impose que V n+1 soit voisin de v et que Cn+1 soit l’une des
couleurs x(v) ou y(v). La probabilité de cet événement est au plus (2∆)/(#V#C).
Pour que d(f (x, Vn+1 , Cn+1 ), f (y, Vn+1 , Cn+1 )) = 0, il suffit que Vn+1 = v et que
Cn+1 soit différent des couleurs des voisins de v. La probabilité de cet événement est au
moins (#C − ∆)/(#V#C).
Par différence, on obtient
  (3∆ − #C)
E d(f (x, Vn+1 , Cn+1 ), d(f (y, Vn+1 , Cn+1 ) − 1 ≤ ,
#V#C
d’où on déduit l’inégalité annoncée.
Le théorème fournit même une minoration de la vitesse de convergence vers la loi
uniforme sur A lorsque #C > 3∆. En effet, notons P Z la loi d’une variable aléatoire Z,
π la loi uniforme sur A et lorsque µ et ν sont deux probabilités sur A, notons d V T (µ, ν)
la distance en variation totale entre µ et ν :
1 X
dV T (µ, ν) = sup |µ(B) − ν(B)| = |µ{x} − ν{x}|.
B⊂C V 2 V
x∈C

Supposons que Y0 ait pour loi π. Alors pour tout n ∈ N, Y n a aussi pour loi π. En
remarquant que
1 X
I[Xn 6=Yn ] = I[Xn =x] − I[Yn =x] ,
2 V x∈C
on montre facilement que
 (3∆ − #C) n  (3∆ − #C) n
dV T (PXn , π) ≤ P [Xn 6= Yn ] ≤ E[Dn ] ≤ E[D0 ] 1 − ≤ #V 1 − .
#V#C #V#C

Suggestions de développement :
1. Montrer que la suite (Xn , Yn )n∈N est une chaı̂ne de Markov.
2. Compléter la démonstration du théorème
3. Justifier la majoration de dV T (PXn , π). Cette majoration vous semble-t-elle opti-
male ?
4. Soit D = {(x, x) ; x ∈ C V } la diagonale de C V × C V . Montrer que si #C > ∆, la
chaı̂ne (Xn , Yn )n∈N finit presque sûrement dans D à partir d’un certain rang. En
déduire que la loi de Xn tend vers la loi uniforme sur A (si A est non vide).

Références

Ce texte est inspiré de l’article de Alan Frieze et Eric Vigoda « A survey on the use
of Markov Chains to randomly sample colouring », pages 53-71 du livre livre édité par
Geoffrey Grimmett et Colin McDiarmid « Combinatorics, Complexity, and Chance : A
tribute to Dominique Welsh », Oxford lecture series in mathematics and its applications
(34), 2007.