Piet Lammers

8 August 2017

The dimer model part I: A first introduction

This post is part of a series on the dimer model. This series is a product of a reading project and it does not include original research. The series closely follows the notes from Richard Kenyon; references that are used throughout the whole series may be found at the end of the first post.

Consider a chessboard covered by thirty-two domino tiles. Let $G=(V,E)$ be the graph with the squares of the board being the vertices and with edges connecting adjacent squares. Each domino tile is associated with an edge of this graph; write $M\subset E$ for the set of edges associated to domino tiles in our configuration. The set $M$ has the property that every vertex is incident with precisely one edge in $M$. The set $M$ is called a dimer cover or perfect matching of $G$.

Definition i.1. Let $G=(V,E)$ be a graph and $M$ a set. Then $M$ is called a dimer cover or a perfect matching of $G$ if it is both a subset of $E$ and a partition of $V$.

The dimer model is the study of the set of all dimer covers of a particular graph. In particular this involves the problem of counting the concerned set, and the study of probability measures on it. For example, we will calculate the number of domino tilings of the chessboard in part III of this series. What's more, new objects will be constructed from dimer covers, allowing us to push forward measures on dimers to measures on these objects.

We restrict ourselves to studying bipartite graphs. Write $G=(V,E)$ for a general bipartite graph, and $B$ and $W$ for its two parts, the sets of black and white vertices respectively. We reserve the letter $M$ for dimer covers of $G$. Every edge in $E$, and thus every edge in a dimer cover, contains both a black and a white vertex. The graph $G$ will always be either planar or toroidal, which allows us to speak of a set of faces $F$. Note that $F$ depends on the actual embedding, but the embedding will either be chosen canonically or it will be irrelevant. We shall see that the theory for planar graphs does not translate immediately to the toroidal setting.

We now introduce two perspectives on the dimer model. First, let $M$ and $M'$ be dimer covers of a finite graph $G$. Then the symmetric difference $M\Delta M':=(M\setminus M')\cup (M'\setminus M)$ is a union of disjoint cycles of $G$. To see this, pick an edge $e\in M\Delta M'$, say it is in $M$. Then $e\not\in M'$, but the white vertex of $e$ is incident with a unique edge $e'\in M'\setminus M$. Similarly the black vertex of $e'$ is incident to a unique edge in $M\setminus M'$. This path uniquely extends until we arrive back at the black vertex of $e$ to close the cycle. This is inevitable as $G$ is finite. Thus, if we sample two dimer covers, we get a cycle structure on $G$ for free! These cycle structures are important combinatorial objects and are therefore studies in their own right. We need the following two definitions.

Definition i.2. Let $M$ and $M'$ be two dimer covers of the finite graph $G$ and let $c$ be the set of all edges in a cycle of $M\Delta M'$. Let $a:c\to\{1,-1\}$ assign value $-1$ to edges in $M$ and $1$ to edges in $M'$. We call the pair $(c,a)$ an alternating cycle of the triple $(G,M,M')$. Write $\operatorname{AltCyc}(G,M,M')$ for the set of alternating cycles of $(G,M,M')$.

Definition i.3. Let $M$ and $M'$ be two dimer covers of the finite graph $G$ and let $c$ be the set of all edges in a cycle of $M\Delta M'$. Direct each edge in $c\cap M$ from black to white and each edge in $c\cap M'$ from white to black, and write $o$ for this collection of directed edges. Note that all edges in $o$ point in the same direction; we call $o$ a directed cycle of the triple $(G,M,M')$. Write $\operatorname{DirCyc}(G,M,M')$ for the set of directed cycles of $(G,M,M')$.

Equipped with Definition i.3, it is easy to construct yet another object that motivates study of the dimer model. Fix a triple $(G,M,M')$. We construct a function $f$ on the set of faces $F$ of $G$ as follows. Let $A\in F$. Then $A$ may be enclosed by a number of cycles in $\operatorname{DirCyc}(G,M,M')$. We define $f(A)$ to be the number of cycles in $\operatorname{DirCyc}(G,M,M')$ that enclose $A$ and are oriented clockwise minus the number of cycles that enclose $A$ and are directed counterclockwise. Note that $f$ assigns value $0$ to the external face, and on adjacent faces $f$ will differ by either $0$ or $1$.

If $M$ and $M'$ are random then $f$ is a random integral function on $F$. For example, if we take $G$ to be the chessboard, then $f$ is a random function on $\{1,...,8\}\times\{1,...,8\}$. The random function $f$ is often presented as the two-dimensional generalisation of a simple random walk in the integers. A simple random walk is defined in terms of independent steps, that determine if the walk goes up or down. The steps determine the “local behaviour” of the walk. The dimers in $M$ and $M'$ do exactly that: they determine the local behaviour of $f$ in that region. To work out the local increments of $f$ it is enough to know the local dimer configuration of $M$ and $M'$. However, there is a crucial difference: where all step of the random walk are independent, the dimers of a dimer covering are not. This makes calculations on the dimer model vastly more complex - and interesting.

In the next post we introduce the Kasteleyn theory - a series of powerful ideas that allow us to express the number of dimer covers of a graph in terms of (a derivative of) the adjacency matrix of that graph. This makes it feasible to calculate the number of perfect matchings of some larger graphs - such as the number of domino tilings of the chessboard.

References

  1. Richard Kenyon, Lectures on dimers (arXiv)
  2. Richard Kenyon, An introduction to the dimer model (arXiv)