\documentclass[a4paper,10pt]{article}


  \usepackage[utf8]{inputenc}
  \usepackage[french]{babel}
  \usepackage{amsmath}
  \usepackage{amssymb}
  \usepackage{amsthm}
  \usepackage{mathrsfs}
  \usepackage{bbm}
  \usepackage{pifont}
  \usepackage{graphicx}

\title{Pavages aléatoires par touillage de dominos}
\author{Élise Janvresse, Thierry de la Rue}

\begin{document}

\maketitle

La physique statistique s'intéresse à l'étude à grande échelle de systèmes formés d'un nombre immense de composantes microscopiques. Une question essentielle est de savoir comment cette multitude d'éléments s'organise en fonction des contraintes qui leurs sont imposées : quelle est la place laissée au hasard ? Quel comportement observe-t-on à l'échelle macroscopique ? Expérimenter dans ce domaine nécessite de pouvoir générer des configurations typiques à l'aide d'algorithmes simulant les effets du hasard.

\section*{Paver avec des dominos}
L'exemple que nous considérons ici est celui des pavages d'une région du plan avec des dominos de taille $2\times 1$. 
Les règles du pavage sont les suivantes : les dominos doivent remplir toute la région et ils ne doivent pas se chevaucher. 
Parmi toutes les façons de paver une énorme région, y a-t-il une tendance générale ? 
%Comment les dominos ont-ils tendance à s'organiser lorsque la région à paver est très grande ? 

%de l'organisation de molécules composées de deux atomes qui se fixent sur une surface. 
%Les physiciens aimeraient comprendre le comportement à l'échelle macroscopique d'un tel système : que peut-on dire d'un pavage ``typique'' ? Observe-t-on toujours le même type d'organisation ? 

%Nous nous intéressons donc aux façons de paver des régions du plan avec ces dominos. 

\medskip
Bien sûr, il n'est pas toujours possible de paver une région donnée. Une condition nécessaire est clairement que la région soit la réunion d'un nombre pairs de carrés de côté 1. 
Et il existe même des régions du plan satisfaisant cette condition qui ne sont pas pavables par des dominos.
%De plus, quand une région est pavable avec des dominos, il n'y a pas en général une unique façon de le faire. 

\medskip
[Paragraphe développable ?

Voici un exemple de pavage impossible : On veut paver l'échiquier écorné suivant (de taille $8\times 8$) auquel on a ôté les cases de deux coins opposés avec des dominos de taille $2\times 1$. La surface à recouvrir est bien la réunion d'un nombre pairs de carrés de côté 1 ($8\times 8 - 2 = 62$), mais cela est pourtant impossible !

\begin{center}
\includegraphics{chiquie.eps}

{\small (figure : chiquie.png)}
\end{center}

En effet, quelle que soit la façon dont un domino est placé, il recouvre une case noire et une case blanche. Or l'échiquier écorné contient plus de cases blanches (32) que de noires (30). Il est donc impossible de le paver avec nos dominos.]



\section*{Pavage aléatoire} 
% Expliquer ce que ça veut dire (chapeau).
% Faire un blabla sur l'intérêt en mécanique statistique... 
% Comment faire en pratique pour tirer au sort un pavage aléatoire ?
% Mentionner l'algorithme de Wilson ?
% Enchaîner sur le cas particulier du diamant aztèque, dont la construction spécifique permet de donner facilement un algorithme pour générer un pavage aléatoire.

Quand une région du plan est pavable avec des dominos, il existe en général un très grand nombre de pavages possibles.
Pour connaître la manière typique dont s'organisent les dominos, il est utile de pouvoir tirer au sort un pavage. 
Mettons tous les pavages possibles dans un chapeau, mélangeons bien et tirons-en un sans regarder. 
C'est ce que l'on appelle un tirage équiprobable : tous les pavages ont la même probabilité d'être choisis. 
En pratique, une telle énumération de tous les pavages est irréalisable : le nombre de pavages possibles augmente extrêmement vite avec la taille de la région à paver. 

Les mathématiciens ont donc mis au point des algorithmes qui permettent de réaliser une telle expérience sans recourir à un chapeau.
Le plus connu utilise le lien avec les ``arbres couvrants''\footnote{Kenyon, Richard W., Propp, James G., Wilson, David B. Trees and matchings. Electron. J. Combin. 7 (2000), Research Paper 25, 34 pp.} et l'algorithme de David Wilson\footnote{Propp, J. and Wilson, D.
How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph. 
7th Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, GA, 1996).
J. Algorithms 27 (1998), no. 2, 170--217.} pour générer ces objets.

Nous allons ici présenter une autre méthode, dite de ``touillage de dominos'' (domino shuffling), pour générer des pavages aléatoires.
Elle a été développée pour une forme très particulière de région, le diamant aztèque, mais peut être généralisée pour réaliser d'autres sortes de pavages.



\section*{L'algorithme du touillage de dominos}

Voici les diamants aztèques d'ordre 1, 2 et 3 et 6 :

\begin{center}
\includegraphics{vide.eps}

{\small (figure : vide.png)}
\end{center}

Il y a bien sûr deux façons de paver le diamant d'ordre 1. 
Pour le diamant d'ordre 2, il est encore possible de recourir au chapeau. On voit qu'il y a une chance sur 8 de tirer l'un des pavages suivants :

\begin{center}
\includegraphics{base2a.eps}

{\small Les 8 pavages possibles du diamant aztèque d'ordre 2. (figure : base2a.png)}
\end{center}

On pourrait aussi énumérer tous les pavages du diamant d'ordre 3, bien que cela commence à être difficile. 
Mais pour le diamant de taille 4, ce n'est déjà plus raisonnable de construire à la main tous les pavages possibles : il en existe 1024 différents. 
En général, on sait montrer qu'il y  a exactement $2^{n(n+1)/2}$ manières de paver un diamant de taille $n$. 
Pour le diamant de taille 100, il y a donc $2^{5050}$ pavages possibles, un nombre qui s'écrit avec plus de 1 500 chiffres !

\medskip
On peut facilement passer du diamant aztèque d'ordre $n-1$ à celui d'ordre $n$ : Il suffit d'ajouter autour une couche supplémentaire. 
C'est cette propriété géométrique qui permet de construire un pavage aléatoire d'un gros diamant, en construisant successivement des pavages des diamants plus petits. 
Au cours de l'exécution de l'algorithme, un certain nombre de choix d'orientation des dominos se présenteront : à chaque fois que cela sera le cas, on tirera à pile ou face pour décider.

Donner l'animation pour paver le diamant d'ordre 10, puis celle sur le diamant d'ordre 100.

[Paragraphe développable ? : Détail de l'algorithme :

On commence par le diamant d'ordre 1 en tirant à pile ou face l'orientation des deux dominos (tous les deux horizontaux ou tous les deux verticaux). 

Comment passer d'un pavage du diamant d'ordre $n-1$ à un pavage du diamant d'ordre $n$ ?
Pour cela, nous avons besoin de la notion de \textit{cellule active}. 
Une \textit{cellule} est un carré $2\times 2$ contenu dans le diamant. 
Ayant colorié les cases du diamant comme sur un échiquier, on peut distinguer deux sortes de cellules : celles dont la case en haut à gauche est noire et celle pour lesquelles elle est blanche. 
Toutes les cellules qui touchent le bord sont de même type. 
Par exemple, dans le diamant d'ordre 2, la case en haut à gauche est blanche (et c'est le cas pour tous les diamants d'ordre pair). 
Nous dirons qu'une cellule est \textit{active} si elle est du même type que celles du bord. 

\begin{center}
\includegraphics{active.eps}

{\small \`A gauche : l'une des 4 cellules actives du diamant d'ordre 2. \`A droite, 3 des 9 cellules actives du diamant d'ordre 3. (figure : active.png)}
\end{center}

On part d'un pavage du diamant d'ordre $n-1$ et on ajoute une couche de cases pour l'insérer dans un diamant d'ordre $n$. 
Considérons une des cellules actives du gros diamant et les dominos complètement contenus dans cette dernière : 
Si elle est recouverte par deux dominos entiers, on enlève les deux dominos. 
Si elle contient exactement un domino entier, on le décale de l'autre côté de la cellule. 
Si elle ne contenait aucun domino entier, on la recouvre avec deux dominos en tirant à pile ou face leur orientation. 

\begin{center}
\includegraphics{mvt.eps}

{\small Exemples de cellule active contenant 2, 1 ou 0 dominos entier. (figure : mvt.png)}
\end{center}

Si l'on applique cette procédure sur chacune des $n^2$ cellules actives du diamant d'ordre $n$, on obtient un pavage de celui-ci.


\begin{center}
\includegraphics{passage.eps}

{\small Passage d'un pavage du diamant d'ordre 2 à un pavage du diamant d'ordre 3. \`A droite, on a tiré au sort les orientations des dominos dans les cellules actives entourées en pointillés. (figure : passage.png)}
\end{center}

]

\section*{Le phénomène du cercle arctique}
Si l'on tire au hasard un des pavages possibles d'un diamant de taille assez grande, on verra, comme sur l'animation ci-dessus,  apparaître avec une probabilité proche de 1 le fameux cercle arctique\footnote{W. Jockusch, J. Propp et P. Shor. Random domino tilings and the arctic circle theorem  (1998). http://fr.arxiv.org/abs/math.CO/9801068} : à l'extérieur du cercle inscrit dans le diamant les dominos sont tous ``gelés'' dans le même sens, alors qu'à l'intérieur le désordre règne.

Le phénomène du cercle arctique dans le pavage aléatoire du diamant aztèque présente un intérêt très particulier : dans ce modèle, les effets de bord se propagent à une grande distance de la frontière du domaine et sont donc visibles à l'échelle macroscopique.
Voici un pavage typique du carré (de côté 60) ; il ne contient pas de zone gelée :


\begin{center}
\includegraphics[width=65mm]{arctic-circle100.eps} \hfill\includegraphics[width=40mm]{carre60.eps}

{\small \`A gauche, un pavage typique du diamant aztèque d'ordre 100. \`A droite, un pavage typique du carré de côté 60. (figures : arctic-circle100.png et  carre60.png)}
\end{center}




\section*{Pavage aléatoire d'autres régions du plan : l'algorithme du touillage avec poids}

Lors de l'application de l'algorithme du touillage, il est nécessaire de tirer à pile ou face pour passer d'un pavage du diamant de taille $n-1$ au pavage du diamant de taille $n$.
On utilise une pièce équilibrée pour décider entre les deux façons possibles d'orienter certains dominos car on ne souhaite pas privilégier un sens plutôt que l'autre. 
Il existe une version\footnote{J. Propp. Generalized domino-shuffling. Theoretical Computer Science 303 (2003), p. 267-301} plus sophistiquée de l'algorithme qui permet de favoriser ou défavoriser certains placements des dominos. 
On associe un poids à chaque position possible d'un domino : la position sera d'autant plus favorisée que le poids est important. 
%On parle dans ce cas d'algorithme du touillage avec poids. 
Les tirages au sort se font alors avec des pièces biaisées (qui favorisent ou défavorisent les piles).

\medskip
En fait, il est même possible d'interdire de placer des dominos à certains endroits en leur attribuant des poids nuls\footnote{\'E. Janvresse, T. de la Rue, Y. Velenik. A note on domino shuffling. Electron. J. Combin. 13 (1) 2006.}. 
C'est ce que l'on a fait pour obtenir un pavage aléatoire du carré de côté 60 présenté plus haut. 
Celui-ci a été ``inséré'' dans un diamant aztèque, et on a interdit certains placements de dominos. 
\begin{center}
\includegraphics{carre_insere.eps}

{\small Un carré de taille $8\times 8$ inséré dans un diamant de taille 8. On interdit que les dominos chevauchent le carré, en attribuant un poids nul aux positions spécifiées en rouge. (figure : carre\_insere.png)}
\end{center}
\`A l'extérieur du carré, les dominos se rangent obligatoirement tous de la même façon (horizontalement en bas et en haut et verticalement à droite et à gauche). 
On obtient, à l'aide de l'algorithme du touillage, un pavage aléatoire équiprobable du carré.

\medskip
Bien sûr, on peut faire la même chose pour paver un rectangle (dont la largeur ou la longueur est paire). 
On peut même s'amuser en attribuant des poids en fonction de l'intensité de pixels d'une photographie. Voilà ce que cela donne :

figure : photo

 \section*{Autres pavages aléatoires}

Il est possible de réaliser des pavages avec d'autres formes que des dominos à partir de l'algorithme du touillage :
par exemple paver un hexagone avec des losanges.

[Paragraphe développable : \textbf{Couplages parfaits d'un graphe}

Pour comprendre le passage à d'autres types de pavages, nous avons besoin de la notion de couplage parfait d'un graphe.
Nous allons associer un graphe à une région formée de cases : 
Les sommets sont les centres de chaque case, et deux sommets appartenant à des cases ayant un côté commun sont reliés entre eux par une arête. 

Chaque arête du graphe correspond à un placement possible d'un domino. 
Partant d'un pavage de la région par des dominos, on considère l'ensemble des arêtes associées : on obtient ainsi un \textit{couplage parfait} du graphe, c'est-à-dire une collection d'arêtes qui recouvrent une fois et une seule chaque sommet du graphe. Inversement, à tout couplage parfait du graphe correspond un pavage par les dominos.

\begin{center}
\includegraphics{graphe.eps}

{\small Lien entre un pavage du diamant d'ordre 3 et un couplage parfait du graphe associé. (figure : graphe.png)}
\end{center}

Attribuer un poids nul à une position de domino revient à effacer l'arête correspondante dans le graphe. 
L'algorithme de touillage avec poids permet alors d'obtenir un couplage parfait de sous-graphes du graphe associé au diamant aztèque.
Cela peut fonctionner même avec des graphes \textit{a priori} différents. 
Par exemple, le graphe associé au réseau hexagonal ci-dessous peut s'identifie à un sous-graphe d'un diamant aztèque assez grand.

\begin{center}
\includegraphics[width=12cm]{regular.eps}

{\small À gauche : un graphe représenté comme un réseau hexagonal. À droite, le même graphe vu comme un sous-graphe du diamant aztèque (les arêtes en pointillés sont effacées par attribution d'un poids nul). (figure : regular.png)}
\end{center}

Une fois généré un couplage parfait du sous-graphe correspondant au réseau hexagonal, on lui associe un pavage de l'hexagone. Cette fois les pavés utilisés ne sont plus des dominos rectangulaires, mais des losanges. Il y en a trois sortes, suivant leur orientation.

\begin{center}
\includegraphics[width=4cm]{hexa-dual-0.eps}\includegraphics[width=4cm]{hexa-dual-1.eps}\includegraphics[width=4cm]{hexa-dual-2.eps}
\end{center}
]

Un pavage typique de l'hexagone à l'aide de losanges fait apparaître un phénomène semblable au cercle arctique dans le diamant aztèque.

\begin{center}
\includegraphics[width=10cm]{arctic_6-6-6.eps}
\end{center}

Il est possible également de paver une région avec plusieurs types de pavés simultanément (carrés, triangles, \textit{etc.}). Dans les exemples ci-dessous, il semble qu'un phénomène de gel des bords soit aussi présent, mais on ne sait pas identifier la forme de la partie gelée.

\begin{center}
\includegraphics[width=8cm]{arctic_4-8-8.eps}

\vspace{1cm}

\includegraphics[width=8cm]{arctic_4-6-12.eps}
\end{center}

\end{document}
