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.

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).

É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.

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.

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.

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 là.

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 là 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