Piet Lammers

9 August 2017

The dimer model part II: Kasteleyn theory

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.

A first objective is to count the number of dimer covers of a given finite graph. The set of dimer covers is a complex combinatorial object; there will usually be too many dimer covers to simply calculate them all and count. The Kasteleyn theory simplifies this counting problem. The main ingredient of the theory is the following observation. If $A$ is the adjacency matrix of $G$ then $$A=\begin{pmatrix}0&D\\D^t&0\end{pmatrix}$$ for some matrix $D$ with its rows indexed by $W$ and its columns by $B$. Write $N:=|B|=|W|$ and pick an enumeration of $B$ and $W$. Then \begin{equation} \label{detk} \operatorname{Det}D:=\sum_{\sigma\in S_N}\operatorname{Sgn}\sigma\prod_{i=1}^ND_{w_i,b_{\sigma(i)}}. \end{equation} The set $\{\{w_i,b_{\sigma(i)}\}:1\leq i\leq N\}$ is a dimer cover of $G$ if and only if $\sigma\in S_N$ produces a nonzero term in (\ref{detk}). In general not all terms in have equal sign due to the appearance of $\operatorname{Sgn}\sigma$. The idea is to multiply each nonzero entry of $D$ by a complex number of modulus one, such that the complex argument of each nonzero term in (\ref{detk}) is the same. Such a collection of numbers is given by a Kasteleyn weighting.

Definition ii.1. A Kasteleyn weighting is a map $k:E\to S^1\subset\mathbb{C}$ such that for any face with edges $(e_1,...,e_{2n})$ in clockwise order, \begin{equation} \frac{k(e_1)k(e_3)\cdot ...\cdot k(e_{2n-1})}{k(e_2)k(e_4)\cdot ...\cdot k(e_{2n})}= (-1)^{1+n}. \label{kweightingdefinition} \end{equation}

To see that Kasteleyn weightings exist, pick a spanning tree of $G$ and fix $k\equiv 1$ on this spanning tree. Then $k$ has a unique extension to $E$ satisfying (\ref{kweightingdefinition}). Write $K$ for the entrywise product of $D$ with $k$.

Theorem ii.2. The number of dimer covers of $G$ equals $|\operatorname{Det}K|$.

To see why $k$ cancels the sign change of $\sigma$ in (\ref{detk}), we need the following lemma.

Lemma ii.3. Let $k$ be a Kasteleyn weighting of $G$ and $(e_1,e_2,...,e_{2n})\subset E$ a cycle enclosing $m$ vertices. Then \begin{equation} \frac{k(e_1)k(e_3)\cdot ...\cdot k(e_{2n-1})}{k(e_2)k(e_4)\cdot ...\cdot k(e_{2n})} =(-1)^{1+n+m}. \label{alternatingproduct} \end{equation}

Proof. Let $(F_i)_{i\geq 0}$ be a sequence of distinct faces such that $\cup_{i\leq j}F_j$ is connected and simply connected for all $j$. It suffices to prove that (\ref{alternatingproduct}) holds for the boundary of $\cup_{i\leq j}F_i$ for all $j$. Write $2n_j$ for the number of boundary edges of $\cup_{i\leq j}F_i$ and $m_j$ for the number of internal vertices. We induct on $j$. For $j=0$ this is just (\ref{kweightingdefinition}); there are no enclosed vertices. Now assume that the statement holds for certain $j$. Write $2n'$ for the number of boundary edges of $F_{j+1}$ and $m'$ for the number of boundary vertices of $F_{j+1}$ that lie in the interior of $\cup_{k\leq j+1}F_k$. The alternating product of $k$ along the boundary of $\cup_{i\leq j+1}F_i$ is the product of the alternating products of $k$ along the boundaries of $\cup_{i\leq j}F_i$ and $F_{j+1}$. By induction, this equals $$(-1)^{1+n_i+m_i+1+n'} =(-1)^{1+(n_{i}+n'-m'-1)+(m_{i}+m')} =(-1)^{1+n_{i+1}+m_{i+1}},$$ so we have established (\ref{alternatingproduct}) for the boundary of $\cup_{i\leq j+1}F_i$.

Proof of Theorem ii.2. Suppose that the permutations $\sigma$ and $\sigma'$ correspond to dimer covers $M$ and $M'$ of $G$ respectively. It suffices to prove that the terms corresponding to $\sigma$ and $\sigma'$ in (\ref{detk}) with $D$ replaced by $K$ are equal, i.e., that \begin{equation} \label{sufficient} \frac{\prod_{i=1}^Nk(\{w_i,b_{\sigma(i)}\})} {\prod_{i=1}^Nk(\{w_i,b_{\sigma'(i)}\})}=\frac{\operatorname{Sgn}\sigma'}{\operatorname{Sgn}\sigma}. \end{equation} On the left hand side of this equation the dimers present in both covers cancel, and as observed last time the remainder of the dimers is organised into a finite number of cycles, $\operatorname{AltCyc}(G,M,M')$. We prove (\ref{sufficient}) for the case that $\operatorname{AltCyc}(G,M,M')$ contains a single cycle; by induction (\ref{sufficient}) follows for general pairs $(M,M')$. Write $2n$ for the length of the unique cycle in $\operatorname{AltCyc}(G,M,M')$. Write $m$ for the number of enclosed vertices. Then $m$ is even, since $M$ is a dimer cover of these enclosed vertices. Thus we can transform $M$ into $M'$ by shifting all dimers along the cycle. The right hand side of (\ref{sufficient}) equals $(-1)^{1+n}$, because the permutations differ by an $n$-cycle. The left hand side of (\ref{sufficient}) equals the alternating product of $k$ along the cycle. The proof is completed by the lemma, observing that $m$ is even.