Le modèle de dimères

(ou comment les mathématiciens jouent aux dominos)

Piste noire 8 juin 2016  - Ecrit par  Adrien Kassel Voir les commentaires

Texte d’invitation au modèle de dimères et ses liens avec la combinatoire, la physique statistique et la géométrie. A l’exception de l’un d’entre eux, les encadrés sont destinés aux lecteurs avertis.

Paver un échiquier $8\times 8$ par des dominos de taille $1\times 2$ consiste à poser les dominos sur l’échiquier de sorte que chacun couvre exactement deux cases et que tout l’échiquier soit ainsi recouvert, sans chevauchement de dominos. Comme il y a $8\times 8=64$ cases dans un tel échiquier, il faut $32$ dominos pour le paver. Une façon simple de le faire consiste à poser tous les dominos dans le même sens (horizontal ou vertical). Ceci n’est pas très intéressant. Un pavage plus intéressant est donné sur la Figure 1 au milieu. Prenez un instant pour réfléchir à toutes les autres façons dont vous pourriez le faire. Un monde s’ouvre, n’est-ce pas ? N’essayez cependant pas d’énumérer toutes les combinaisons possibles, ce serait insensé : il y en a 12 988 816. Mais ce n’est pas tout ! Si l’on modifie très légèrement la donne et que l’on se fixe maintenant comme but de recouvrir par $31$ dominos l’échiquier dont on a préalablement ôté les cases de deux coins opposés, on est vite coincé. Cette modification en apparence anodine s’avère radicale et il faut se rendre à l’évidence que la tâche est impossible (nous laissons le soin aux lecteurs d’en trouver la raison simple ; voir aussi plus bas).

Figure 1

De gauche à droite : un échiquier standard qui admet 12 988 816 recouvrements par des dominos ; un tel recouvrement ; un échiquier écorné qui n’admet aucun recouvrement par des dominos

Afin de mieux comprendre cette histoire d’échiquier et de dominos, tentons d’en extraire et d’en abstraire la substantifique moelle. Au vu de la question que l’on se pose, quelle information devons-nous vraiment retenir de la situation précédente ? On retient qu’il y a des cases noires et blanches qui alternent (deux cases de même couleur ne sont pas adjacentes) et que lorsque l’on dépose un domino sur l’échiquier, on établit une liaison entre une case blanche et une case noire.

La manière standard d’encoder mathématiquement ces données utilise la théorie des graphes. On remplace l’échiquier par un graphe fini (un ensemble fini de sommets connectés par des arêtes) et biparti (les sommets sont coloriés noirs et blancs de manière alternée) de telle sorte que les sommets noirs correspondent aux cases noires et les sommets blancs aux cases blanches. Déposer un domino revient à choisir une arête dans le graphe. Ainsi, au lieu de devoir recouvrir l’échiquier par des dominos, le but du jeu est maintenant de choisir un ensemble d’arêtes (nécessairement disjointes) qui relient tout sommet noir à un (unique) sommet blanc. On appelle cela un couplage parfait. En voici une illustration (sur un petit échiquier de taille $4\times 4$, par souci de lisibilité).

Figure 2

En haut, un échiquier $4\times 4$ et un de ses recouvrements par des dominos ; en bas, le graphe biparti associé, et le couplage parfait correspondant

Combinatoire et complexité

Dans l’exemple de l’échiquier écorné, il est très facile de démontrer qu’il n’existe pas de couplage parfait puisqu’une condition nécessaire à l’existence d’un couplage parfait est qu’il y ait autant de cases noires que de cases blanches (un domino recouvre exactement deux cases : l’une noire, l’autre blanche).

Ce n’est pas une condition suffisante, comme le montre l’exemple de l’échiquier à la forme particulière de la Figure 3  [1].

Figure 3

Une portion de l’échiquier de départ contenant autant de cases noires et blanches qui n’admet pourtant pas de recouvrement par 4 dominos. Ceci illustre l’importance de la forme du domaine à recouvrir.

Dans le cas général, déterminer si un graphe biparti admet un couplage parfait peut se faire au moyen du critère de Hall : un graphe biparti admet un couplage parfait si et seulement si pour tout sous-ensemble de sommets noirs (resp. de sommets blancs), le nombre de sommets blancs (resp. de sommets noirs) qui lui sont voisins excède la taille du sous-ensemble. On peut vérifier ce critère sur l’exemple de la Figure 3. Une jolie application de ce critère à un problème de géométrie a été décrite ici.

Pour aller plus loin

Trouver un couplage explicite est un problème relativement sympathique dans la mesure où il existe un algorithme pour le faire (appelé algorithme hongrois) qui s’exécute en temps polynomial en le nombre de sommets  [2]. On dit que ce problème est dans la classe de complexité $\mathsf{P}$.

La question de déterminer le nombre total de combinaisons lorsqu’il en existe (comme dans notre exemple de départ) est bien plus difficile. On peut l’exprimer en utilisant le langage de la théorie de la complexité (ces notions ont été abordées dans ces pages). Ce problème est dans la classe $\mathsf{\# P}$ (c’est un théorème célèbre de Leslie Valiant obtenu en 1979), ce qui veut dire, en admettant  [3] que $\mathsf{P}\subsetneq \mathsf{NP}$, qu’il n’existe pas d’algorithme permettant de calculer ce nombre de manière exacte en temps polynomial.

Ce problème fait d’ailleurs partie de la liste connue de problèmes $\mathsf{\# P}$-complets. À ce titre, pour montrer qu’un problème de comptage est dans la classe $\mathsf{\# P}$, il suffit de montrer qu’il est au moins aussi difficile que de compter le nombre de couplages parfaits d’un graphe. On trouvera plus de détails sur les aspects combinatoires et algorithmiques des couplages (en particulier, leur décompte approximatif) dans l’ouvrage de référence LP09.

Le fait que l’on puisse déterminer explicitement le nombre de couplages parfaits dans le cas d’un échiquier de taille $8\times 8$ est une exception due au fait que le graphe est planaire  [4]. Ce résultat important est dû au physicien néerlandais Pieter Kasteleyn (Hol96) qui en 1961 obtint une formule exacte pour le nombre de couplages parfaits de tout graphe planaire. La formule utilise une notion de base d’algèbre linéaire, le déterminant d’une matrice, qui peut se calculer en temps polynomial en la taille de la matrice (par des méthodes de transformations élémentaires de la matrice comme la méthode du pivot de Gauss).

Crash course d’algèbre linéaire

Pour les lecteurs n’ayant pas encore rencontré cette notion, une matrice est simplement un tableau de nombres ou de symboles. Voici par exemple une matrice de taille $3\times 3$ :
\[M_0=\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}\,.\]

Le déterminant d’une matrice $M=(m_{k,\ell})_{1\le k,\ell\le n}$ de taille $n\times n$ est une somme sur les permutations  [5] de l’ensemble $\{1,\ldots,n\}$ d’un certain signe $\varepsilon(\sigma)=\pm 1$ (que l’on appelle la signature de la permutation) multiplié par le produit des coefficients déterminés par la permutation. Plus précisément
\[\det M=\sum_{\sigma\in \mathcal{S}_n}\varepsilon(\sigma)\prod_{k=1}^n m_{k,\sigma(k)}\,,\]
où $\mathcal{S}_n$ désigne le groupe  [6] des permutations sur $n$ éléments. Dans notre exemple, on obtient
\[\det M_0=aei-afh-bdi+bfg+cdh-ceg\,.\]
Il y a ici $6$ termes, mais pour une matrice de taille $n\times n$, on doit sommer $n!$ termes.

Le permanent est un nombre associé à une matrice $M$ qui diffère du déterminant seulement par le retrait du signe $\varepsilon(\sigma)$, c’est-à-dire  [7]
\[\mathrm{perm}\, M=\sum_{\sigma\in \mathcal{S}_n}\prod_{k=1}^n m_{k,\sigma(k)}\,.\]
Dans notre exemple, on obtient
\[\mathrm{perm}\, M_0=aei+afh+bdi+bfg+cdh+ceg\,.\]

Étant donné un graphe biparti, avec $n$ sommets noirs et $n$ sommets blancs que l’on suppose numérotés de $1$ à $n$, introduisons la matrice d’adjacence $A$, dont les lignes sont indexées par les sommets noirs et les colonnes par les sommets blancs et dont les seuls coefficients (notés $a_{k,\ell}$) non nuls correspondent aux paires de sommets $(k,\ell)$ qui sont voisins et dans ce cas le coefficient vaut $1$. Le nombre de couplages parfaits d’un tel graphe biparti est \[N=\sum_{\sigma\,\text{permutation de}\,\{1,\ldots,n\}}\,\prod_{k=1}^n a_{k,\sigma(k)}\,.\]
Le membre de droite de cette équation est par définition le permanent de la matrice $A$ et on le note $\mathrm{perm}\,A$.

Par exemple, dans le cas d’un graphe biparti complet sur $2n$ sommets ($n$ sommets noirs sont reliés à $n$ sommets blancs, en autorisant toute les liaisons possibles), on a
\[|\mathcal{S}_n|=n!=1\times 2\times\cdots\times n\]
recouvrements possibles.

Contrairement au déterminant, calculer le permanent d’une matrice est difficile en général et il n’existe pas d’algorithme efficace pour le faire.

Pour aller plus loin

Si la matrice est à coefficients $0$ ou $1$, le problème de calculer son permanent est même un problème $\mathsf{\# P}$-complet. Et en effet, c’est bien la même chose que de compter le nombre de couplages parfaits d’un graphe biparti ! Jusque là, on n’a fait que réexprimer le problème dans le langage de l’algèbre linéaire.

L’idée de Kasteleyn a été de démontrer que lorsque le graphe est planaire et biparti, on peut toujours construire une matrice $K$ obtenue à partir de $A$ (la matrice d’adjacence des sommets noirs versus blancs) par une modification très simple  [8] en insérant des signes $\pm$ de telle sorte que les signes $\varepsilon(\sigma)$ soient compensés et que l’on ait
\[\det K=\mathrm{perm}\, A\,,\]
c’est-à-dire en mots : déterminant de $K$ égal le permanent de $A$.
Grâce à cette idée, le dénombrement des couplages parfaits d’un graphe planaire passe du statut de problème difficile (calcul d’un permanent) à celui de problème plus simple (calcul d’un déterminant). On dit que $K$ est une matrice de Kasteleyn.

Dans le cas de notre premier exemple, l’échiquier $8\times 8$, une légère modification de la méthode de Kasteleyn proposée par Jerome Percus puis Richard Kenyon, montre que l’on peut considérer pour $K$ la matrice carrée d’adjacence de sommets noirs versus blancs, où le coefficient d’indice $x,y$ vaut $1$ si les sommets $x,y$ sont reliés verticalement, $i$ s’ils sont reliés horizontalement, et $0$ sinon. Ici $i$ est le nombre complexe (imaginaire pur) tel que $i^2=-1$.

Considérons d’abord un exemple très simple (Figure 4) pour illustrer la méthode.

Figure 4

Dans cet exemple, on a numéroté les sommets noirs et blancs afin de pouvoir associer au graphe ses matrices d’adjacence $A$ et de Kasteleyn $K$, toutes deux indexées par les sommets noirs (lignes) et les sommets blancs (colonnes).

Dans ce cas, la matrice d’adjacence est
\[A=\begin{pmatrix}1 & 1 & 0\\ 1 & 1 & 1\\ 0 & 1 & 1\end{pmatrix}\,,\]
et la matrice de Kasteleyn associée est
\[K=\begin{pmatrix}1 & i & 0\\ i & 1 & i\\ 0 & i & 1\end{pmatrix}\,,\]
d’où l’on trouve que $\det K=3$ et $\mathrm{perm}\, A=3=\det K$, qui est bien le nombre de couplages parfaits de ce graphe.

Pour l’échiquier $8\times 8$, la matrice de Kasteleyn est de taille $32\times 32$ mais en la diagonalisant en utilisant les symétries du problème  [9], son déterminant se transforme en le produit suivant :
\[|\det K|=\prod_{k=1}^8\prod_{\ell=1}^8\sqrt{\left\vert 2\cos\left(\frac{\pi k}{9}\right) +2 i \sin\left(\frac{\pi \ell}{9}\right)\right\vert}=12\,988\,816=2^4\times 17^2\times 53^2\,,\]
ce qui donne le résultat annoncé [10].

Plus généralement, le nombre $N_n$ de couplages parfaits d’un échiquier de taille $2 n\times 2n$ est répertorié, dans l’Encyclopédie en ligne des suites de nombres entiers, par la suite A004003 (OEIS). Cette suite croît exponentiellement avec $n^2$ : on peut montrer qu’asymptotiquement lorsque $n$ tend vers l’infini, on a
\[N_n=\exp\left[\frac{4}{\pi} C n^2(1+o(1))\right]\,,\]
où \[C=1-\frac{1}{3^2}+\frac{1}{5^2}-\frac{1}{7^2}+\cdots=\int_{0}^1 \frac{\arctan x}{x}\, dx=0.915\ldots\]
est la constante dite de Catalan (du nom du mathématicien franco-belge Eugène Charles Catalan)  [11].

Le cas d’un réseau hexagonal est aussi intéressant, voir Figure 5. Les dominos dans ce cas s’apparentent à des losanges et l’on peut voir un recouvrement comme la projection d’une surface dans l’espace (un empilement de cubes). Dans le cas d’une portion hexagonale du réseau hexagonal (dont la longueur des côtés est $a,b,c,a,b,c$, où $a,b,c$ sont trois entiers), le nombre de recouvrements est le produit
\[\prod_{i=1}^a\prod_{j=1}^b\prod_{k=1}^c\frac{i+j+k-1}{i+j+k-2}\,.\]
Ce calcul est antérieur au résultat de Kasteleyn et c’est un cas particulier de la célèbre formule de Percy MacMahon pour compter le nombre de partitions d’un entier. Dans l’exemple de la Figure 5 cette formule montre qu’il y a $50$ recouvrements possibles.

Figure 5

Au centre : Un pavage par des losanges d’une région hexagonale où $a=b=2$ et $c=3$. En utilisant la formule de MacMahon énoncée plus haut, on trouve qu’il y a $50$ recouvrements possibles de cette région. À gauche : la représentation sous-forme de couplage parfait de ce pavage. À droite : on peut interpréter le pavage comme un empilement de cubes ; les nombres indiquent la hauteur de l’empilement par rapport au plan horizontal de référence si chaque cube a des côtés de longueur $1$.

Dans la suite, on supposera tous les graphes bipartis et planaires.

Physique statistique

Dans les années 60, Kasteleyn, qui avait aussi une formation de chimiste, cherchait à comprendre un modèle de polymères en solution. À cause de la difficulté du problème général, il fut contraint de se restreindre à un cas particulier, celui d’une solution de dimères (polymères n’ayant qu’une liaison). C’est ce que l’on appelle aujourd’hui le modèle de dimères. Si Kasteleyn s’est intéressé aux problèmes des couplages, c’est en lien avec ce modèle  [12].
D’un point de vue physique, on peut penser que c’est l’adsorption de molécules diatomiques à la surface d’un cristal en solution que l’on modélise. Dans ce cas un dimère est une molécule diatomique et pour décrire le modèle de dimères, on pense à un dimère comme à une arête d’un couplage parfait d’un très grand graphe fini qui modélise la structure du cristal. Pour comprendre ce phénomène, la physique statistique nous amène alors à étudier un couplage parfait aléatoire. Dans la suite il sera donc question de mesures de probabilité sur l’ensemble des couplages parfaits.

Pour aller plus loin

En physique statistique, on associe à toute arête $e$ un poids $\nu(e)>0$ (représentant le logarithme d’une forme d’énergie interne) et on peut définir le poids total d’un couplage comme étant le produit des poids sur les arêtes du couplage. Pour un graphe fini, la somme pondérée sur tous les couplages parfaits possibles
\[\mathcal{Z_\nu}=\sum_{\omega}\prod_{e\in\omega}\nu(e)\]
est appelée la fonction de partition du modèle. Dans le cas où tous les poids sont égaux à $1$, la fonction de partition n’est rien d’autre que le nombre de couplages parfaits.
La mesure de probabilité que l’on considère associe à tout couplage $\omega$ une probabilité
\[\mathbb{P}(\omega)=\frac{\prod_{e\in\omega}\nu(e)}{\mathcal{Z_\nu}}\,.\]

D’un point de vue physique et mathématique il est intéressant d’étudier les mesures de probabilité sur les couplages parfaits d’un graphe infini, que l’on supposera périodique. On imagine donc un graphe biparti plan infini bipériodique comme le réseau carré. Mais attention, ce graphe est pondéré (par des poids que l’on suppose aussi périodiques).

On ne s’intéresse pas à toutes les mesures possibles. Une première contrainte évidente est que l’on impose l’invariance par translation, ce qui représente une forme d’isotropie du modèle. Deux principes physiques déterminent les caractéristiques supplémentaires que doivent vérifier les mesures de probabilité dignes d’intérêt. La première provient de la théorie du physicien américain Josiah Willard Gibbs des systèmes à l’équilibre thermodynamique qui prédit la structure que doit prendre une mesure de probabilité : en bref, la mesure dans une région donnée doit être invariante par ré-échantillonage dans une région disjointe (les mesures de Gibbs du modèle d’Ising ont été abordées ici). La deuxième est issue de l’hypothèse d’ergodicité formulée par le physicien autrichien Ludwig Boltzmann. En jargon mathématique technique on parle de mesure de Gibbs ergodique.

Probabilités et géométrie algébrique

Dans un travail remarquable de 2003, Richard Kenyon, Andrei Okounkov et Scott Sheffield sont parvenus à classifier et décrire très précisément toutes les mesures de Gibbs ergodiques du modèle de dimères sur un graphe planaire bipériodique. Essayons d’esquisser les grandes lignes heuristiques de ce résultat majeur.

Si un domaine fondamental  [13] du graphe contient $d$ sommets de chaque couleur, il existe un polynôme (de Laurent, c’est-à-dire avec des monômes aux exposants négatifs aussi) explicite $P$ en deux variables de degré $d$, appelé polynôme caractéristique, qui sert de brique élémentaire pour calculer toutes les quantités intéressantes du modèle.
Par exemple si le graphe est le réseau hexagonal (avec tous les poids égaux à $1$), le domaine fondamental est représenté dans la Figure 6, $d=1$ et on a
$P(z,w)=1+z+1/w$.

Figure 6

Un domaine fondamental du réseau hexagonal dont le polynôme caractéristique est $P(z,w)=1+z+1/w$ et le polygone de Newton associé

Le polygone de Newton de $P$ est l’enveloppe convexe $\mathcal{N}(P)$ des points entiers $(i,j)\in\mathbb{Z}^2$ tels que $z^iw^j$ soit un monôme de $P$. Voir Figure 6 pour le polygone de Newton associé au réseau hexagonal.
Un théorème de Sheffield établit que le polygone de Newton $\mathcal{N}(P)$ de $P$ donne une paramétrisation de toutes les mesures de probabilité de Gibbs ergodiques.

Pour comprendre comment un point de $\mathcal{N}(P)$ correspond à une mesure de probabilité il faut introduire un autre objet associé à un couplage parfait : sa fonction de hauteur. La représentation d’un pavage par une fonction de hauteur remonte à John Conway, et fut popularisée par William Thurston (Thu90).

La fonction de hauteur est une fonction à valeurs entières sur les faces internes du graphe (les faces internes sont les composantes connexes bornées dans le complémentaire du graphe dans le plan : dans le réseau carré ce sont les carrés unités, dans le réseau hexagonal, les hexagones). Il y a une certaine liberté dans le choix de sa définition. Pour le graphe carré (de notre échiquier), on la définit souvent comme suit (à une constante additive près). Étant donné sa valeur $h$ en une face, elle est définie sur les autres faces en suivant la règle donnée sur la figure qui suit : lorsqu’on se déplace le long d’un domino (indépendamment de sa position horizontale ou verticale), la fonction de hauteur diminue de $1$ lorsqu’on longe un sommet noir sur la gauche (et donc un sommet blanc sur la droite) et augmente de $1$ lorsqu’on longe un sommet blanc sur la gauche (et donc un sommet noir sur la droite).

Pour définir la fonction partout, on commence par étendre la fonction aux faces adjacentes à un même domino, puis de proche en proche à toutes les faces (ce procédé est bien défini).

Cette définition peut paraître un peu mystérieuse mais on verra plus tard qu’elle donne lieu à de jolies formes limites. Il est important de comprendre que la fonction de hauteur, ou plus précisément la différence de deux fonctions de hauteur, a pour lignes de niveaux des chemins formés par des doubles-dominos comme sur la Figure 7, et ceci fournit une définition plus directe valable pour tout graphe biparti planaire comme nous l’expliquons maintenant.

Modulo un facteur multiplicatif, on peut définir cette fonction comme suit (voir Figure 7) : elle associe à toute face intérieure du graphe un entier. On se donne deux sacs de dominos : les uns sont bleus, les autres rouges. Construisez un premier recouvrement bleu. Par-dessus, déposez un recouvrement rouge. On retire les paires de dominos qui se superposent exactement. Maintenant regardons ce qu’il reste. Il s’agit de boucles simples de longueur paire. De plus, elles sont orientées si l’on convient qu’un cycle hérite de l’orientation noir-blanc recouverte par les dominos rouges. En fixant la valeur de la fonction sur une face, on la définit pour les autres faces en ajoutant $+1$ ou $-1$ chaque fois que l’on croise un cycle orienté dans le sens horaire, ou anti-horaire.
Étant donné la configuration bleue, cette méthode associe une fonction à tout recouvrement rouge. La fonction de hauteur n’est pas unique et afin de la déterminer il faut préciser un choix de référence (ceci peut s’exprimer en termes de conditions aux bords qui correspondent au choix du recouvrement bleu).

Figure 7

À gauche : deux recouvrements de dominos superposés ; À droite : les cycles associés et leur fonction de hauteur

Il se trouve que dans le cas d’un réseau hexagonal, (le graphe de) la fonction de hauteur n’est rien d’autre (à un coefficient de proportionnalité près) que la surface dont le pavage est une projection lorsqu’on le voit comme un empilement de cubes (voir l’exemple Figure 5).

Si l’on se fixe un domaine borné dans le plan dont le bord est analytique et qu’on le discrétise par une portion finie du graphe infini avec un maillage très fin de telle sorte qu’il en existe des recouvrements par dimères, on peut regarder la suite de tirages aléatoires de recouvrements. On obtient alors (après remise à l’échelle) une surface limite pour la fonction de hauteur correspondante (c’est une sorte de loi des grands nombres) qui est une surface minimale déterminée par sa tension de surface ; c’est un théorème de Henry Cohn, Richard Kenyon et James Propp. La pente de cette surface reflète l’aléa local du pavage, et en particulier, près du bord, il n’y a plus d’aléa : la configuration est gelée et on parle de forme limite. Voir un exemple Figure 8  [14].

Sheffield a démontré que l’ensemble des gradients (les pentes dans les deux directions de coordonnées) possibles est $\mathcal{N}(P)$ mais le lien entre une pente $(s,t)$ et la mesure de probabilité correspondante est très subtil  [15]. Pourtant il est possible de comprendre heuristiquement ce lien comme nous allons le voir maintenant.

Comme on peut le voir sur la simulation  [16] de la Figure 8, certaines parties sont plus figées et d’autres plus aléatoires. Il existe une classification de cet aléa qui imite la classification physique usuelle : état gazeux, liquide ou solide (gelé). Pour décrire ce diagramme de phase de manière élégante, Kenyon, Okoukov et Sheffield ont eu recours à un changement de variable subtil en utilisant un autre ensemble associé au polynôme $P$, son amibe.

Pour aller plus loin

L’amibe $\mathcal{A}(P)$ d’un polynôme $P$  [17] est définie comme l’image en coordonnées logarithmique du module des éléments de l’ensemble $\{(z,w)\in\mathbb{C}^2\quad\text{tels que}\quad P(z,w)=0\}$, appelé courbe spectrale de $P$. Autrement dit,
\[\mathcal{A}(P)=\{(\log|z|,\log|w|)\quad\text{tels que}\quad P(z,w)=0\,\,\text{et}\,\,(z,w)\in\mathbb{C}^2\}\,.\]
L’amibe associée à notre exemple est donnée Figure 8.

Lorsque l’amibe a la même aire que le polynôme de Newton, on dit que la courbe spectrale est de Harnack. Ceci est lié à des propriétés algébriques de la courbe (Mikhalkin, Rullgård).

Un des résultats du travail de Kenyon, Okounkov et Sheffield est d’avoir démontré que la courbe spectrale d’un modèle de dimères est une courbe de Harnack. Kenyon et Okounkov ont de plus démontré le résultat spectaculaire que toute courbe de Harnack est la courbe spectrale d’un tel modèle de dimères.

On pourra consulter les textes de survol de Kenyon (Ken07) et Felder (Fel07) pour plus de détails.

Figure 8

À gauche : une forme limite dans un domaine approché par le réseau hexagonal (échantillonnée par Richard Kenyon) ; À droite : l’amibe du polynôme $P(z,w)=1+z+1/w$ associé au réseau hexagonal.

Grâce au changement de variables sus-mentionné, on peut reparamétrer l’espace des mesures de Gibbs ergodiques par $\mathbb{R}^2$ (au lieu de $\mathcal{N}(P)$) de telle sorte que l’amibe $\mathcal{A}(P)$ soit un diagramme de phase. Dans l’exemple de la Figure 8, la zone bleue correspond aux mesures liquides et l’extérieur aux mesures gelées.

Pour observer des mesures gazeuses, il faut regarder un exemple plus compliqué. Considérons le réseau carré pondéré dont un domaine fondamental est donné par celui de la Figure 9. Les mesures gazeuses correspondent aux zones blanches à l’intérieur de l’amibe.

Figure 9

Un domaine fondamental d’un graphe infini pondéré dont le polynôme caractéristique est $P(z,w)=9-2w+1/w^2-7/w+1/z+z/w$ ; le polygone de Newton associé ; l’amibe correspondante. L’amibe représente le diagramme de phase : la zone blanche à l’extérieur correspond aux mesures gelées, la zone bleue aux mesures liquides, et les deux zones blanches à l’intérieur aux mesures gazeuses.

Un autre exemple qui fournit des mesures gazeuses a été étudié dans le cas du domaine déterminé par un diamant aztèque. Sur la Figure 10, on voit bien les trois différentes phases qui sont du centre vers l’extérieur : gazeuse, liquide et solide.

Figure 10

Un modèle de dimère échantillonné sur un graphe carré pondéré dans un domaine borné avec forme de diamant aztèque (tourné de 45 degrés par commodité). À gauche : les dimères (par Sunil Chhita) — on distingue nettement les trois phases (les dominos sont de 4 couleurs en fonction de leur orientation et de la parité de leurs coordonnées sur le réseau carré, ici tourné de 45 degrés). Dans les 4 coins, les dominos sont alignés : la phase est gelée) ; dans une région circulaire vers l’intérieur, on a une phase liquide ; et enfin au centre, l’aléa est le plus grand : la phase est gazeuse. À droite : la fonction de hauteur (par Vincent Beffara - les couleurs ici sont purement esthétiques et n’ont pas la même signification qu’à gauche).

Le domaine fondamental du graphe pondéré sous-jacent est donné dans la Figure 11, avec le polygone de Newton et l’amibe associée.

Figure 11

Domaine fondamental d’un graphe carré pondéré, infini bipériodique. Son polynôme caractéristique est $P(z,w)=-(5/2) - 1/(2 w) - w/2 - 1/(2 z) - z/2$ dont le polygone de Newton et l’amibe sont représentés. Le trou au centre de l’amibe correspond à la phase gazeuse.

On pourra se référer aux notes de cours de Kenyon (Ken09) pour plus de détails sur le sujet. On pourra aussi consulter la récente parution FdT15.

Géométrie conforme et fractals aléatoires

Nous avons parlé plus haut de la limite de la fonction de hauteur lorsque la maille du graphe tend vers zéro (on parle de limite d’échelle). On peut comprendre ce résultat de convergence comme une loi des grands nombres. Cette limite est très sensible à la forme du domaine mais aussi au type de graphe périodique qui l’approche.

Mais qu’en est-il de ses fluctuations (le théorème central limite, en somme) ? Et qu’en est-il des cycles associés aux recouvrements des dominos bleus et rouges ?

Il se trouve qu’il existe des objets aléatoires universels sous-jacents indépendants de la structure microscopique du pavage. Ces objets oublient en quelque sorte toute la complexité du pavage, mais n’en retiennent que les fluctuations aléatoires.

Sous de bonnes hypothèses (voir les travaux de Richard Kenyon, Béatrice de Tilière, et plus récemment Leonid Petrov) les fluctuations de la fonction de hauteur dans une région liquide du diagramme de phase convergent vers le champ libre gaussien (voir Figure 12), une distribution (au sens de Laurent Schwartz) aléatoire [18].

Figure 12

Un champ libre gaussien

Et il est conjecturé  [19] que les boucles du modèle de double-dominos convergent vers l’ensemble conforme de boucles de paramètre $\kappa=4$ (voir Figure 13). Cet ensemble de boucles fait partie d’une famille à un paramètre d’objets fractals introduite par Scott Sheffield et Wendelin Werner en 2010.

Figure 13

Un ensemble conforme de boucles de paramètre $\kappa=4$ (échantillonné par David Wilson)

Ces deux objets fractals aléatoires partagent deux propriétés fondamentales : la propriété de Markov (ce qui se passe dans deux parties disjointes éloignées est indépendant l’un de l’autre) et l’invariance conforme. C’est cette deuxième notion qui fait le lien avec la géométrie complexe. Elle signifie que si l’on transforme le domaine en un autre par une application qui préserve les angles localement (une telle application est dite conforme), alors la loi de ces deux objets aléatoires est inchangée. On en a parlé sur ce site ici et .

Depuis 20 ans, l’étude probabiliste de la géométrie conforme (ou théorie conforme des champs en physique) est en pleine expansion. On en a déjà parlé ici et sur ce site. D’importants progrès ont été réalisés depuis avec notamment l’avènement récent de la géométrie dite imaginaire, notamment grâce aux travaux d’Oded Schramm, Wendelin Werner, Greg Lawler, Scott Sheffield, Jason Miller, Julien Dubédat, Bertrand Duplantier et bien d’autres. Voir aussi les articles reliés ici et là : Bef15. Deux des objets les plus importants de cette théorie sont l’ensemble conforme de boucles de paramètre $\kappa=4$ et le champ libre gaussien.

Ces objets fractals possèdent des propriétés fascinantes. En particulier, on peut donner un sens à l’assertion suivante : les boucles de l’ensemble conforme de boucles (Figure 13) sont les lignes de niveau du champ libre gaussien (Figure 12). Du point de vue de leurs analogues discrets (c’est-à-dire des fonctions de hauteur), c’est la définition, mais le démontrer pour les objets fractals est une autre paire de manches !

Problèmes ouverts

Il semble raisonnable de penser que le jeu de domino que nous avons présenté est loin d’avoir fini d’inspirer les progrès scientifiques. En guise de conclusion, nous évoquons trois domaines de recherche actifs reliés aux dominos.

En algorithmique et optimisation combinatoire, de nombreux problèmes appliqués nécessitent des algorithmes efficaces pour trouver un couplage parfait (le problème dit des affectations) d’un immense graphe possédant certaines propriétés (par exemple si c’est un graphe creux, c’est-à-dire qui a peu d’arêtes par rapport au nombre de ses sommets, ou alors au contraire si le graphe est dense) et il est important de les optimiser. Calculer de manière approchée le nombre de possibilités s’avère aussi important.

En physique, il est intéressant de considérer des modèles de polymères plus proches de la réalité. Mais la méthode de Kasteleyn ne marche alors plus. Certains modèles autorisent des interactions entre les dominos ou considèrent des graphes qui ne sont plus planaires. Des percées dans la première direction ont été effectuées récemment par un groupe de chercheurs italiens (Alessandro Giuliani, Vieri Mastropietro, Fabio Lucio Toninelli) en utilisant les idées de la théorie physique dite du flot de renormalisation.

D’un point de vue mathématique (en combinatoire et géométrie) il est tentant de changer les règles de départ et de remplacer le domino par d’autres tuiles élémentaires comme des triminos (taille $1\times 3$), d’autres rectangles allongés, ou d’autres polyominos. Dans ce cas, les techniques mentionnées plus haut ne s’appliquent plus directement, et il faut en inventer de nouvelles.

[Bef15]
Vincent Beffara, Raconte moi... le processus SLE, Gaz. Math. (144), 59—63, 2015. Lien

[Fel07]
Giovanni Felder, The work of Andrei Okounkov, In International Congress of Mathematicians. Vol. I, 55—64, Eur. Math. Soc., Zurich, 2007. Lien

[FdT15]
Patrick Ferrari et Béatrice de Tilière, Dimer models and random tilings, Panoramas et Synthèses, SMF, 2015.

[Hol96]
Frank den Hollander, Pieter Willem Kasteleyn : October 12, 1924 — January 16, 1996, Journal of Statistical Physics, 85(5):801—806, 1996. Lien

[Ken07]
Richard Kenyon, Les travaux d’Andrei Okounkov sur le modèle des dimères, Gaz. Math., (112):18—22, 2007. Lien

[Ken09]
Richard Kenyon, Lectures on dimers, In Statistical mechanics, volume 16 of IAS/Park City Math. Ser., 191—230. Amer. Math. Soc., Providence, RI, 2009. Lien

[LP09]
László Lovász et Michael D. Plummer, Matching theory, AMS Chelsea Publishing, Providence, RI, 2009.

[OEIS]
Neil J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Lien

[Oll]
Yann Ollivier, La borne de Jacobi.
Lien

[Thu90]
William P. Thurston, Conway’s tiling groups, Amer. Math. Monthly, 97(8):757—773, 1990. Lien1,Lien2

Post-scriptum :

Je remercie Nicolas Curien, Béatrice de Tilière et Sanjay Ramassamy pour des échanges au sujet de ce texte, ainsi que Vincent Beffara, Sunil Chhita, Richard Kenyon et David Wilson de m’avoir autorisé à utiliser leurs simulations numériques. Je remercie aussi Serge Cantat, Clément Caubel, Cidrolin, cmarchetti, Bastien Mallein et Marielle Simon pour leur relecture et leurs commentaires.

Article édité par Nicolas Curien

Notes

[1Thurston (Thu90) discute de conditions nécessaires plus raffinées ainsi que de conditions suffisantes pour l’existence de pavages, mais nous n’en parlerons pas. Ces conditions sont basées sur la notion de fonction de hauteur que nous introduirons plus bas.

[2Cet algorithme, que nous ne décrivons pas ici, est dû à Kuhn en 1955 et s’appuie sur les travaux antérieurs des mathématiciens hongrois Egerváry et Kőnig. Des améliorations successives de cet algorithme sont dues à Munkres en 1957, et Hopcroft et Karp en 1972. Il semble cependant (Oll) qu’un algorithme en temps polynomial ait déjà été proposé par le mathématicien allemand Jacobi au début du XIXe siècle, comme l’atteste un texte posthume en latin.

[3Décider de la validité de cette assertion demeure un problème ouvert majeur à ce jour, médiatisé par la mise à prix de sa solution par le Clay Mathematics Institute.

[4Un graphe est dit planaire s’il peut être dessiné dans le plan sans que ses arêtes ne se croisent. Le graphe de la Figure 2 est planaire. Un exemple de graphe non planaire est le graphe complet sur 5 sommets, c’est-à-dire un pentagone avec toutes ses diagonales.

[5Une permutation de $n$ éléments est un réordonnement de ces éléments supposés ordonnés au départ : par exemple lorsque l’on part de $(1,2,3)$ et que l’on associe $(2,1,3)$, c’est une permutation sur $3$ éléments.

[6Pour ceux qui ne connaissent pas encore cette notion, un groupe est un ensemble muni d’un produit. Dans le cas des permutations, cette structure de produit vient du fait que l’on peut composer deux permutations pour en obtenir une troisième.

[7De manière plus prosaïque, le permanent d’une matrice $n\times n$ est une somme de produits de coefficients de la matrice : chaque produit contient exactement un coefficient de chaque ligne et un coefficient de chaque colonne et la somme porte sur toutes les façons de choisir $n$ coefficients vérifiant ces conditions.

[8Il suffit de choisir les signes de telle sorte que leur produit le long de toute face (une face est une composante connexe du complémentaire du graphe dans le plan) soit $(-1)^{\ell/2+1}$ où $\ell$ est le nombre d’arêtes bordant la face ; nous laissons en exercice aux lecteurs le soin de vérifier qu’un tel choix est possible (indication : utiliser un arbre couvrant) et qu’il donne le résultat escompté. Plus généralement, la méthode de Kasteleyn s’applique à tous les graphes planaires, y compris ceux qui ne sont pas bipartis ; dans le cas général, le choix des signes est un peu plus subtil et repose sur la notion d’orientation de Kasteleyn. De plus, il faut cette fois considérer la matrice d’adjacence totale et prendre la racine carrée du déterminant.

[9La diagonalisation est un type particulier de modification d’une matrice par des transformations élémentaires qui laisse le déterminant inchangé. Toutes les matrices ne sont pas diagonalisables mais celle-ci l’est car elle est symétrique. De plus, comme le graphe sous-jacent est très régulier, on peut faire le calcul explicitement facilement.

[10Il peut paraître surprenant qu’un produit de nombres compliqués (avec les fonctions trigonométriques) donne un entier : c’est pourtant le cas puisque le déterminant d’une matrice à coefficients entiers est entier, même si ses valeurs propres (obtenues par diagonalisation) sont des nombres réels non-entiers. Pour faire le calcul, un ordinateur donnera facilement 12 988 816. Nous ne détaillons pas ce calcul ici, et renvoyons le lecteur curieux à un récent article qui propose une autre démonstration de cette formule (valable pour des échiquiers rectangulaires de taille $2n\times 2m$) comme un produit de valeurs spéciales de polynômes de Tchebychev de seconde espèce.

[11Une autre suite, sans doute plus familière aux lecteurs, la suite de Fibonacci
\[\forall n\ge 2,\, u_n=u_{n-1}+u_{n-2},\quad u_0=0,u_1=1\,,\]
qui croît exponentiellement comme les puissances du nombre d’or,
s’interprète aussi en termes de dominos : le $n$-ième terme de cette suite compte le nombre de recouvrements d’un échiquier rectangulaire de taille $2\times n$. Cet exercice classique se résout facilement sans recourir à la méthode de Kasteleyn.

[12L’importance du modèle de dimères tient aussi au fait que l’on peut étudier le modèle d’Ising par son biais. Ce modèle a été introduit en 1920 par le physicien allemand Wilhelm Lenz, alors directeur de thèse du physicien allemand Ernst Ising, comme un modèle simplifié d’interaction magnétique. L’étude du modèle d’Ising en dimension $2$ via le modèle de dimères a été développée par Kasteleyn, et parallèlement par les physiciens anglais Michael Fisher et Harold Temperley. Cette approche a permis de comprendre en détails le modèle d’Ising en dimension $2$. Une introduction à ce modèle est parue ici.

[13Un domaine fondamental désigne une plus petite portion du graphe qui détermine le graphe infini par translation dans deux directions.

[14La forme limite circulaire obtenue dans le cas d’une forme particulière, appelée diamant aztèque (une certaine portion du réseau carré), a été décrite dans ces pages. Voir aussi la vidéo récente sur ce sujet dans le cadre des 5 minutes Lebesgue.

[15Pour les spécialistes : l’énergie libre de la mesure de probabilité associée à $(s,t)$ est donnée par le dual de Legendre évalué en $(s,t)$ de la fonction de Ronkin de $P$.

[16Une méthode pour échantillonner le modèle de dimères par ordinateur utilise la technique Coupling from the past de Propp—Wilson.

[17Cette notion a été introduite par I. M. Gelfand, M. M. Kapranov et A. V. Zelevinsky dans un livre influent en 1994.

[18Même si le champ aléatoire représenté sur la Figure 12 paraît déjà très irrégulier, ce que l’on voit ici est en fait une régularisation par approximation discrète de l’objet réel — l’objet lui-même n’est pas une fonction, et on ne peut donc pas dessiner son graphe.

[19Les travaux récents de Richard Kenyon et de Julien Dubédat accréditent cette thèse.

Partager cet article

Pour citer cet article :

Adrien Kassel — «Le modèle de dimères» — Images des Mathématiques, CNRS, 2016

Crédits image :

Figure 8 - Richard Kenyon
Figure 13 - David Wilson
Figure 10 - Sunil Chhita et Vincent Beffara

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM