text:
# Dimers, Tilings and Trees

## 1 Introduction

In , Temperley gave a bijection between the set of spanning trees of an $`n\times n`$ grid and the set of perfect matchings (dimer coverings) of a $`(2n1)\times (2n1)`$ grid with a corner removed. This bijection was generalized in  to a weight-preserving bijection (the KPW construction) from the set of in-directed spanning trees (also known as arborescences) on an arbitrary weighted, directed planar graph $`𝒢_T`$ to the set of perfect matchings on a related graph $`𝒢_D`$. The construction is useful in statistical mechanics because certain types of events in the spanning tree model can be easily computed using dimer technology, for example winding numbers of branches and local statistics. For dimer models arising from a spanning tree model, moreover, the spanning tree formulation provides other useful information. In particular Wilson’s algorithm  for generating spanning trees can be used to rapidly simulate dimer configurations. Moreover, the spanning tree formulation identifies natural boundary conditions (“Temperleyan” boundary conditions) for the dimer model which allows asymptotic computation of many properties, in particular conformal invariance properties of dimers . However in the paper  it was not known if every dimer model on a bipartite planar graph corresponded to a spanning tree model on a related graph.

A seemingly unrelated construction is the construction of a “Smith diagram” from a planar resistor network . This is a tiling of a plane region with squares of arbitrary sizes, which is associated in a bijective way to a critical-point-free harmonic function on the network with unit resistances (there is a square in the tiling for each edge in the graph, whose size is proportional to the current flow through the edge). This construction was generalized in  to planar Markov chains (graphs with transition probabilities), where a harmonic function gives a tiling with trapezoids. It was not known at the time what if any graphical correspondence was natural for general polygonal tilings.

In the current paper we extend the above equivalences and describe a correspondence between these three types of objects: weighted bipartite planar graphs, planar Markov chains, and tilings with general convex polygons.

In particular from a weighted bipartite planar graph $`𝒢_D`$ we can construct a tiling $`T`$ of a plane region with convex polygonal tiles, and a planar Markov chain $`𝒢_T`$, in an essentially bijective way (that is, up to natural equivalences). There is a tile in $`T`$ for each “white” vertex of $`𝒢_D`$, whose shape is determined by a discrete analytic function (see definitions below). The graph $`𝒢_T`$ is a graph on the $`1`$-skeleton of the tiles, with transitions determined by their Euclidean geometry. The tilings are therefore representations of discrete analytic functions on the bipartite planar graph $`𝒢_D`$, which correspond to harmonic functions on the Markov chain $`𝒢_T`$.

An important application of this construction is that it provides a converse to the Temperley-KPW construction. That is, starting with the finite weighted bipartite planar graph $`𝒢_D`$, one constructs a Markov chain $`𝒢_T`$ and a measure-preserving bijection from the dimer model on $`𝒢_D`$ to the spanning tree process on $`𝒢_T`$. This dimer/spanning tree correspondence has a number of important consequences. Firstly, it was used in  in a fundamental way to classify Gibbs measures on dimer models on infinite periodic planar graphs. Secondly, since spanning trees can be sampled efficiently , the construction provides a way to sample efficiently from bipartite planar dimer models. Previously the only (provably efficient) way to sample general planar bipartite dimer models was to do exact computations of joint edge probabilities. A third application  is that it allows one to compute the asymptotics of dimer correlations and height fluctuations in terms of the Green’s function on $`𝒢_T`$.

In Section 5 we discuss how the construction extends in the case of infinite periodic graphs. This is motivated by the study of the dimer model on periodic graphs, see . Given any periodic planar bipartite weighted graph $`𝒢_D`$, we produce an essentially unique “almost periodic” planar Markov chain $`𝒢_T`$, which extends the dimer/spanning tree correspondence. This unicity is an important element in the classification theorem of ergodic Gibbs measures on dimer coverings of $`𝒢_D`$ described in .

Acknowledgement. We thank Andrei Okounkov for several ideas and discussions.

## 2 Definitions

### 2.1 Dimers and measures

Let $`𝒢_D=(V,E)`$ be a finite bipartite planar graph. Bipartite means that the vertices $`V`$ can be $`2`$-colored, that is, colored black and white so that black vertices are only adjacent to white vertices and vice versa. Let $`\nu :E(0,\mathrm{})`$ be a weight function on the edges. A perfect matching, or dimer configuration $`ME`$ is a set of edges with the property that each vertex is contained in exactly one edge in $`M`$. The weight of a matching $`M`$ is $`\nu (M)=_{eM}\nu (e)`$. Let $`(𝒢_D)`$ denote the set of perfect matchings of $`𝒢_D`$. Let $`\mu `$ be the probability measure on $`(𝒢_D)`$ giving a matching a probability proportional to its weight: $`\mu (M)=\frac{1}{Z}\nu (M)`$ where $`Z=_{M(𝒢_D)}\nu (M).`$

### 2.2 Kasteleyn matrices

If $`𝒢_D`$ has $`n`$ black and $`n`$ white vertices, a Kasteleyn matrix (see ) for $`𝒢_D`$ is a real $`n\times n`$ matrix $`K=(K_{i,j})`$ whose rows index the black vertices and columns index the white vertices of $`𝒢_D`$, defined as follows. The entry $`K_{i,j}`$ is zero if there is no edge from $`b_i`$ to $`w_j`$, and if

there is an edge of weight $`\nu (b_iw_j)`$ then $`K_{i,j}=\pm \nu (b_iw_j)`$, where the signs are chosen so that the product of signs of edges around every interior face of $`K`$ is $`(1)^{d/2+1}`$, where $`d`$ is the degree of the face. This property of signs is not changed if we multiply all elements in a particular column or row of $`K`$ by $`1`$ (because each vertex of $`𝒢_D`$ has an even number—zero or two—of edges on each face of $`𝒢_D`$). Moreover, such a choice of signs always exists, and by Kasteleyn’s theorem, the determinant of $`K`$ is (up to sign) the sum of the weights of the matchings of $`𝒢_D`$ (). By a discrete analytic function we mean a function $`f`$ on black vertices (resp. white vertices) which satisfies $`fK=0`$ (resp. $`Kf=0`$). This generalizes the definition of discrete analytic function on $`^2`$ defined in . These functions play a role implicitly in sections 4 and 5.

### 2.3 Gauge transformations

If we multiply the weights of all the edges in $`𝒢_D`$ having a fixed vertex by a constant, the measure $`\mu `$ does not change, since exactly one of these weights is used in every configuration. More generally, two weight functions $`\nu _1,\nu _2`$ are said to be gauge equivalent if $`\nu _1/\nu _2`$ is a product of such operations, that is, if there are functions $`f_1`$ on white vertices and $`f_2`$ on black vertices so that for each edge $`wb`$, $`\nu _1(wb)/\nu _2(wb)=f_1(w)f_2(b).`$ Gauge equivalent weights define the same measure $`\mu `$.

Multiplying the $`i`$th row (resp., column) of a Kasteleyn matrix $`K`$ by a positive, non-zero constant $`c`$ is equivalent to multiplying by $`c`$ the weights of all of the edges of $`𝒢_D`$ incident to $`b_i`$ (resp., $`w_i`$). In other words any matrix $`\stackrel{~}{K}`$ obtained from $`K`$ by multiplying the rows and columns of $`K`$ by non-zero constants will be a Kastelyn matrix for a graph which is gauge equivalent to $`𝒢_D`$.

## 3 T-graphs and corresponding dimer/spanning-forest models

In this section, we define a family of planar graphs called T-graphs and describe a weight-preserving correspondence between the spanning trees on a T-graph and dimer configurations on a bipartite graph derived from it. This is closely related to the result of , who also give a relation between spanning trees on a general planar graph and dimers on a derived graph.

In the present context however our derivation can be reversed: we will see in Section 4 that for every bipartite planar graph, which is non-degenerate in the sense that it contains no edges which fail to be used in any perfect matching of the graph (for the purposes of the dimer model, it makes sense to delete these edges), endowed with a generic choice of weights, there is a gauge-equivalent graph which can be derived from a T-graph in this way. By taking limits, the correspondence generalizes to the case when the weights are not assumed to be generic.

### 3.1 Complete edges that form T-graphs

The definition of $`T`$-graph on a torus—which we use in section 5—is quite simple. A disjoint collection $`L=\{L_1,L_2,\mathrm{},L_n\}`$ of open line segments in the torus $`^2/^2`$ forms a T-graph in the torus if $`_{i=1}^nL_i`$ is closed. The term “T-graph” refers to the fact each endpoint of a given $`L_i`$ necessarily lies on the interior of some $`L_j`$ with $`ji`$. In other words, each $`L_i`$ “tees into” an $`L_j`$ at each of its two endpoints.

We say a disjoint collection $`L_1,L_2,\mathrm{},L_n`$ of open line segments in $`^2`$ forms a T-graph in $`^2`$ if $`_{i=1}^nL_i`$ is connected and contains all of its limit points except for some set $`R=\{r_1,\mathrm{},r_m\}`$, where each $`r_i`$ lies on the boundary of the infinite component of $`^2`$ minus the closure $`\overline{L}`$ of $`_{i=1}^nL_i`$. Elements in $`R`$ are called root vertices. For example, a single open line segment forms a T-graph with root vertices given by the two endpoints. A pair of open line segments—one of which tees into the other to make the letter “T”—forms a T graph with three root vertices. The three open edges of a triangle also form a T-graph with three root vertices. A partitioning of a convex polygon $`P`$ into convex polygonal tiles using a finite number of line segments will form a $`T`$-graph with root vertices at the vertices of $`P`$ if and only if it is generic in the sense that the endpoint of each of these line segments lies either on the interior of another line segment or on the boundary of $`P`$. (See Figure 1.)

Note that each endpoint of a given $`L_i`$ is either a root vertex or an interior point of some $`L_j`$. To distinguish the $`L_i`$ from subsegments of the $`L_i`$ (which we discuss later) we refer to the $`L_i`$ as complete edges.

In subsequent subsections, we will use $`L`$ to define a weighted, directed graph $`𝒢_T(L)`$ and a weighted, bipartite graph $`𝒢_D(L)`$. The ultimate goal of this section will be to derive a weight-preserving bijection between directed spanning forests on $`𝒢_T(L)`$ (with specified roots) and perfect matchings of $`𝒢_D(L)`$. When the choice of $`L`$ is clear from the context, we write $`𝒢_T=𝒢_T(L)`$ and $`𝒢_D=𝒢_D(L)`$.

### 3.2 T-graphs and their duals

The set $`V_T(L)`$ of vertices of $`𝒢_T`$ (the graph we will call the tree-graph of $`L`$) is the set of points in $`^2`$ which are endpoints of at least one of the $`L_i`$. A vertex $`v`$ which is in the interior of a complete edge $`L_i`$ (called an interior vertex) has exactly two edges in $`𝒢_T`$ directed outwards from it: these edges point towards the two immediate neighbors, $`v_1`$ and $`v_2`$, along $`L_i`$ (one on each side of $`v`$). The weights on the edge from $`v`$ to these two $`v_i`$ are chosen in such a way that the two weights add up to one and are inversely proportional to the Euclidean distances $`|vv_i|`$. These weights correspond to the transition probabilities of a Markov chain on $`V_T(L)`$. The root vertices are sinks of $`𝒢_T`$ (they have no outgoing edges in $`𝒢_T`$) and are fixed points of the Markov chain. Note that (by our choice of transition probabilities) the expected change in Euclidean position during a step of the Markov chain is always zero; thus, a random walk on $`𝒢_T`$ — viewed as a Markov chain on positions in $`^2`$ — is a martingale. In other words, the coordinate functions on the vertices of $`𝒢_T`$ are harmonic functions on $`𝒢_T`$ away from the root vertices.

See Figure 2 for an example of a T-graph with three roots. Note that, by convention, when we have transitions both from $`i`$ to $`j`$ and from $`j`$ to $`i`$, rather than drawing two directed edges in the graph $`𝒢_T`$ we draw a single edge with two transition probabilities, one from each end.

We define $`𝒢_T^{}=𝒢_T^{}(L)`$, an undirected dual graph of $`𝒢_T`$, as follows. Let $`C`$ be an arbitrary simple closed curve that encircles the $`_{i=1}^nL_i`$ and contains each of the root vertices $`r_1,\mathrm{},r_m`$ in clockwise order. The vertices of $`𝒢_T^{}`$ are the bounded faces of $`𝒢_TC`$ (bounded connected components of $`^2\backslash (_{i=1}^nL_iC)`$). Faces of $`𝒢_TC`$ adjacent to $`C`$ are called outer faces of $`𝒢_T`$: they correspond to outer vertices of $`𝒢_T^{}`$. Two vertices of $`𝒢_T^{}`$ are connected by an edge $`a`$ of $`𝒢_T^{}`$ if the corresponding faces of $`𝒢_T`$ are adjacent across an edge of $`𝒢_T`$. For an edge $`e`$ of $`𝒢_T`$ we denote by $`e^{}`$ its corresponding dual edge.

###### Lemma 3.1

If $`L_1,L_2,\mathrm{},L_n`$ form a T-graph, then $`𝒢_T`$ has exactly $`n+1`$ faces (including outer faces). Hence $`𝒢_T^{}`$ has $`n+1`$ vertices.

Proof: This follows from Euler’s formula. The line segments $`L_i`$ decompose the interior of $`C`$ into some number $`n_2`$ of open faces (open $`2`$-cells), $`n_1=n`$ open complete edges, and $`n_0=0`$ vertices. Since $`n_2n_1+n_0=1`$, the Euler characteristic of the disc, the result follows. $`\mathrm{}`$

### 3.3 Spanning trees

A spanning tree of a graph $`G`$ is a subset of edges which is connected, contains no cycle, and passes through every vertex. If the edges of $`G`$ are directed, a directed spanning tree, or arborescence, is a spanning tree in which every vertex but one (called the root vertex) has a unique outgoing edge. Given a subset of vertices of $`G`$ called root vertices, a directed spanning forest is a set of edges with no cycles, passing through all vertices, each non-root vertex having a unique outgoing edge, and each component of which is connected to a unique root vertex.

We will employ the following correspondence between (non-directed) spanning trees in $`𝒢_T^{}`$ and their (non-directed) dual spanning forests in $`𝒢_T`$. Using the correspondence between edges of $`𝒢_T^{}`$ and edges of $`𝒢_T`$, we can think of edge subsets of both $`𝒢_T`$ and $`𝒢_T^{}`$ as subsets of the set of all edges of $`𝒢_T`$. Using this interpretation, we state the following lemma (which is illustrated in Figure 3):

###### Lemma 3.2

The complement of a spanning tree $`𝒯`$ of $`𝒢_T^{}`$ is a spanning forest $``$ of $`𝒢_T`$, with roots at the root vertices. Similarly, the complement of a spanning forest $``$ of $`𝒢_T`$, with roots at the root vertices, is a spanning tree $`𝒯`$ of $`𝒢_T^{}`$.

Proof: We sketch the standard tree dualization argument. If $``$ is a spanning forest of $`𝒢_T`$, with roots at root vertices, its complement $`𝒯`$ cannot contain any cycles in $`𝒢_T^{}`$ (since such a cycle would separate at least one interior vertex of $`𝒢_T`$ from the root vertices), and it must be connected (since otherwise, the set of edges separating two components would either form a cycle in $`𝒢_T`$ or a path connecting two root vertices in $`𝒢_T`$); hence it is a spanning tree. Similarly, if $`𝒯`$ is a spanning tree of $`𝒢_T^{}`$, its complement $``$ cannot contain cycles of $`𝒢_T`$ (since such a cycle would separate at least one inner face of $`𝒢_T`$ from the outer faces) and each connected component of $``$ contains at least one root vertex (since otherwise the set of edges separating that component of $``$ from its complement would form a cycle in $`𝒢_T`$). $`\mathrm{}`$

### 3.4 Dimer graphs from $`T`$-graphs

Now we will define the weighted, bipartite (non-directed) graph $`𝒢_D=𝒢_D(L)`$. First, we define a slightly larger $`𝒢_D^r=𝒢_D^r(L)`$, whose black vertices are the $`n`$ complete edges $`L_i`$ and whose white vertices are the $`n+1`$ faces of $`𝒢_T`$ (including outer faces).

A white vertex $`w`$ of $`𝒢_D^r`$ is adjacent to a black vertex $`b`$ of $`𝒢_D^r`$ if the face $`F`$ corresponding to $`w`$ contains a portion of the $`L_i`$ corresponding to $`b`$ as its boundary. The weight $`\nu ((w,b))`$ is then given by the Euclidean length of the portion of the line segment. The graph thus defined is planar. To see this, note that it can be drawn on top of the tiling $`\overline{L}`$ as follows: put a white vertex in the interior of each face, and a black vertex in the center of each complete edge. When $`w`$ and $`b`$ are connected, draw a line from $`w`$ inside the corresponding face towards the complete edge corresponding to $`b`$, and then along this complete edge, staying just to one side, until the center is reached. It is not hard to see that this can be done in such a way that the paths do not intersect.

The graph $`𝒢_D`$ is formed from $`𝒢_D^r`$ by (arbitrarily) picking one of the outer white vertices of $`𝒢_D^r`$ and removing it; we will refer to the removed vertex as the dual root of $`𝒢_D`$. Now, $`𝒢_D`$ is a weighted bipartite graph with $`n`$ white and $`n`$ black vertices. To every edge $`e=(w,b)`$ in a perfect matching of $`𝒢_D`$ (where $`w`$ corresponds to a face $`F`$ and $`b`$ to a complete edge $`L_i`$), we denote by $`S_e`$ the segment of the $`L_i`$ which borders $`F`$. Because of our choice of weights, $`\mu (M)`$ (where $`\mu `$ is the probability measure on perfect matchings defined in the introduction) is proportional to $`_{eM}|S_e|`$ where $`|S_e|`$ is the Euclidean length of $`S_e`$. Now, the edge segment $`S_e`$ may have vertices of $`𝒢_T`$ in its interior; these vertices divide $`S_e`$ into subsegments, each of which has vertices of $`𝒢_T`$ as its endpoints and hence corresponds to an edge of $`𝒢_T`$. A marked matching of $`𝒢_D`$ is a matching $`M`$ of $`𝒢_D`$ together with a specified subsegment $`S_e^{}`$ of $`S_e`$ (which, again, we may interpret as an edge in $`𝒢_T`$) for each $`eM`$. We extend $`\mu `$ to give a measure on random marked matchings as follows: to sample a random marked matching, first choose a random matching. Then for each edge $`e`$, choose an $`S_e^{}`$ from among the subsegments of $`S_e`$, where probability of each subsegment is proportional to its length. If $`M^{}`$ is a marked matching, then $`\mu (M^{})`$ is proportional to $`_{eM}|S_e^{}|`$.

### 3.5 From dimers to trees

Let $`𝒯_M^{}=\{S_e^{}:eM\}`$ be the set of of edges corresponding to a marked matching $`M^{}`$ of $`𝒢_D`$. Each $`S_e^{}`$ corresponds to an edge of $`𝒢_T^{}`$, so we can think of $`𝒯_M^{}`$ as a subgraph of $`𝒢_T^{}`$. We direct each such edge of $`𝒯_M^{}`$ (corresponding to some $`S_e^{}`$) of this graph from the face which corresponds to a vertex in $`e`$ towards the face which does not. We use this interpretation of $`𝒯_M^{}`$ (as a directed subgraph of $`𝒢_T^{}`$) in the following lemma:

###### Lemma 3.3

If $`M^{}`$ is a marked matching, then $`𝒯_M^{}`$ is an in-directed spanning tree of $`𝒢_T^{}`$, rooted at the dual root. The dual $`_M^{}`$ of $`𝒯_M^{}`$ is thus a spanning forest of $`𝒢_T`$ (when $`𝒢_T`$ is viewed as an undirected graph).

Proof: It is sufficient to prove that $`𝒯_M^{}`$ has no directed cycles, since it contains exactly one edge pointing away from each face of $`𝒢_T`$ (excluding the dual root). This is accomplished using Euler’s formula. Suppose that $`𝒯_M^{}`$ had a directed cycle $`F_0,F_1,\mathrm{},F_j=F_0`$ of faces of $`𝒢_T`$. Let $`S_i`$ be the segment $`S_e^{}`$ separating $`F_i`$ and $`F_{i+1}`$. Let $`C^{}`$ be a simple closed curve which starts in the interior of $`F_0`$, passes through $`S_0`$ at one point, moves through the interior of $`F_1`$, passes through $`S_1`$ at a single point, etc. until it returns to $`F_0`$. Except for its intersections with the $`S_i`$’s, each at a single point, $`C^{}`$ is entirely contained in the union of the interiors of the $`F_i`$. The intersection of the $`L_i`$ with the interior of $`C^{}`$ gives a decomposition of this interior into $`n_2`$ two-cells (where $`n_2`$ is the number of faces partial or completely contained inside the loop $`C^{}`$), $`n_1`$ open one-cells and $`n_0=0`$ vertices. Thus, by Euler’s formula $`n_2n_1+n_0=n_2n_1=1`$. In particular $`n_2+n_1`$ is odd.

However, the sequence $`w_0,b_0,w_1,b_1,\mathrm{},b_{j1},w_j=w_0`$ (where $`w_i`$ is the white vertex of $`𝒢_D`$ corresponding to $`F_i`$ and $`b_i`$ is the black vertex corresponding to the complete edge containing $`S_i`$) is a cycle in $`𝒢_D`$, alternating edges of which are contained in $`M`$. The set of vertices in $`𝒢_D`$ enclosed by this cycle must be matched only with each other in a perfect matching (since the cycle disconnects these vertices from the rest of the graph). This is a contradiction to the fact that $`n_2+n_1`$ is odd. $`\mathrm{}`$

Let $`\mu _F`$ be the measure on directed spanning forests of $`𝒢_T`$, rooted at the root vertices, for which $`\mu _F()`$ is proportional to the product of the weights of the edges in $``$. Since each of the two outgoing edges of a given interior vertex has weight (by construction) inversely proportional to its Euclidean length, $`\mu _F()`$ is inversely proportional to the product of the lengths of the edges of $``$; hence, $`\mu _F()`$ is also proportional to the product of the Euclidean lengths of all edges of $`𝒢_T`$ which do not appear (directed one way or another) in $``$.

The following is the main result of this section.

###### Theorem 3.4

The map $`M^{}_M^{}`$ gives a one-to-one correspondence between marked matchings of $`𝒢_D`$ and in-directed spanning forests of $`𝒢_T`$, rooted at $`R`$. The correspondence is measure preserving, i.e., $`\mu (M^{})=\mu _F(_M^{})`$.

Proof: First, we would like to interpret $`_M^{}`$ as a directed spanning forest of $`𝒢_T`$ by orienting each edge of $`_M^{}`$ towards its root vertex. In order to do this, we must check that if $`M^{}`$ is a perfect matching of $`𝒢_D`$, then the directed path along $`_M^{}`$, from a vertex $`v`$ to a root vertex, is a directed path of $`𝒢_T`$. To see this, note first $`_M^{}`$ contains all but one segment of each of the $`L_i`$; thus, for every interior vertex $`v`$ of $`𝒢_T`$ (interior to some $`L_i`$), $`_M^{}`$ includes a path from $`v`$ to exactly one of the endpoints of $`L_i`$. Call this vertex $`v_1`$; each of the directed edges in the directed path from $`v`$ to $`v_1`$ is a directed edge of $`𝒢_T`$. If $`v_1`$ is also an interior vertex of some $`L_j`$, then there is a path of edges in $`_M^{}`$ from $`v_1`$ to some endpoint $`v_2`$ of $`L_j`$. Iterating this process, we must eventually produce a directed path from $`v`$ to a root (since $`_M^{}`$ has no cycles).

It now follows immediately from Lemma 3.3 and our choice of weights, that $`\mu _F(_M^{})`$ is proportional to $`\mu (M^{})`$, since each is proportional to the same product of edge lengths. The proof we will be complete once we show that the map $`M^{}_M^{}`$ is invertible.

Let $``$ be an arbitrary directed spanning forest $``$, rooted in $`R`$. Since only the endpoints of a given $`L_i`$ have outgoing edges pointing to vertices not on $`L_i`$, each vertex of $`L_i`$ belongs to a path pointing to one of the two endpoints. It follows that $``$ must include all but one of the subsegments of $`L_i`$. By Lemma 3.2, the dual of $``$ is a spanning tree of $`𝒢_T^{}`$, which we may view as being directed towards the dual root. Each face $`F`$ of $`𝒢_T`$ is (besides the dual root) is directed towards another face across an edge segment of one of the $`L_i`$. Pairing of $`F`$ with the edge segment produced in this way gives a marked matching $`M^{}`$ for which $`_M^{}=`$. $`\mathrm{}`$

### 3.6 T-graphs and dimers on the torus

If $`L=\{L_1,\mathrm{},L_n\}`$ forms a T-graph on the torus, then we can construct $`𝒢_T=𝒢_T(L)`$ exactly as above; in this case, $`𝒢_T(L)`$ has no root vertices and no outer faces. Since the faces of $`𝒢_T`$ and open edges $`L_i`$ give a decomposition of the torus into one-cells and two-cells, Euler’s formula implies that $`𝒢_T`$ has exactly $`n`$ faces. We construct $`𝒢_D`$ as above (with white vertices given by faces $`F`$ of $`𝒢_T(L)`$, black vertices by the complete edges $`L_i`$, and edges occurring between $`F`$ and $`L_i`$ that share a line segment, weighted according to the length of that segment). We also construct $`𝒢_T^{}`$ in a similar fashion.

A cycle-rooted spanning forest $``$ of $`𝒢_T`$ is a (directed) subgraph of $`𝒢_T`$—with one outgoing edge from each vertex of $`𝒢_T`$—which has no null-homotopic (directed) cycles (i.e., no cycles which—when lifted to the universal cover of the torus—start and end at the same place). The “roots” of such an $``$ are the directed cycles of $``$. Clearly, every such $``$ has at least one (non-null-homotopic) directed cycle.

The dual of $``$ is a cycle-rooted spanning forest $`^{}`$ on $`𝒢_T^{}`$. Now, if $``$ has exactly $`j`$ cycles, then it is not hard to see that $`^{}`$ has $`j`$ cycles as well. We can view $`^{}`$ as a directed cycle-rooted spanning forest by directing each edge not on a cycle towards its cycle root; and then orienting all of the edges in a given cycle one of the two possible directions (there are $`2^j`$ ways of doing this). The proof of the following is now similar to the proof of Theorem 3.4.

###### Theorem 3.5

There is a one-to-one weight preserving correspondence between perfect matchings on $`𝒢_D`$ and in-directed cycle-rooted spanning forests $`^{}`$ on $`𝒢_T^{}`$ whose dual cycle-rooted spanning forests $``$ are in-directed, cycle-rooted spanning forests of $`𝒢_T`$.

T-graphs in a torus can be extended to give periodic T-graphs on the plane, finite subsets of which correspond to finite subgraphs of infinite lattice graphs, such as the grid graph in Example 4.

## 4 T-graphs from dimer graphs

In this section, we describe a procedure for generating $`𝒢_T`$ from $`𝒢_D`$ that applies whenever the so-called Kastelyn matrix fails to have certain degeneracies. Before we begin the construction, we will define Kastelyn matrices and say a word about the kinds of graphs for which these degeneracies occur.

### 4.1 Cuts, and breakers

Say a square matrix $`K`$ is $`k`$-degenerate if it has an $`(nk)\times (nk)`$ minor whose determinant is zero; otherwise it is $`k`$-non-degenerate. The following lemma follows from the standard correspondence between determinants of $`k`$ minors of $`K^1`$ and $`(nk)`$ minors of $`K`$:

###### Lemma 4.1

$`K`$ is $`0`$-non-degenerate if and only if it is invertible. Assuming $`K`$ is invertible, $`K`$ is $`k`$-non-degenerate if and only if $`K^1`$ is $`(nk)`$-non-degenerate.

Suppose now $`K`$ is a Kasteleyn matrix for a bipartite planar graph $`𝒢_D`$. The following is immediate:

###### Lemma 4.2

If $`K`$ and $`\stackrel{~}{K}`$ are gauge equivalent, then $`K`$ is $`k`$-degenerate if and only if $`\stackrel{~}{K}`$ is $`k`$ degenerate

A bipartite graph is balanced if it contains an equal number of black and white vertices. A $`k`$-cut $`A`$ of a balanced bipartite graph $`𝒢_D`$ is subset of the vertices for which:

1. $`A`$ contains at least one white vertex
2. $`A`$ contains $`k`$ more black vertices than white vertices
3. Each edge of $`𝒢_D`$ that connects $`A`$ to its complement has a black vertex in $`A`$.

Note that if $`A`$ is a $`k`$-cut, then its complement would be a $`k`$-cut if the colors black and white were reversed. In particular, the existence of $`k`$ cuts does not depend on which of the two ways we choose to color the vertices. Also, if $`A`$ is a $`k`$-cut of $`𝒢_D`$, then by adding black vertices to $`A`$ and/or removing white vertices from $`A`$, we can construct $`m`$-cuts for any $`kmn1`$. An obvious parity argument implies the following:

###### Lemma 4.3

If $`A`$ is a $`k`$-cut of $`𝒢_D`$, then any perfect matching of $`𝒢_D`$ contains exactly $`k`$ edges which connect $`A`$ to its complement; each of these edges matches a black vertex of $`A`$ and a white vertex of its complement.

A $`k`$-breaker is a subset $`S`$ of the vertices of $`𝒢_D`$ with exactly $`k`$ white and $`k`$ black vertices for which the induced subgraph $`𝒢_D\backslash S`$ of $`𝒢_D`$ has no perfect matchings.

###### Lemma 4.4

If $`𝒢_D`$ is a connected, balanced, bipartite graph, then $`𝒢_D`$

1. has a $`(1)`$-cut if and only if it has no perfect matching.
2. has a $`0`$-cut if and only if $`𝒢_D`$ contains unused edges (i.e., edges which occur in no perfect matching of $`𝒢_D`$).
3. generally has a $`k`$-cut if and only if has a $`(k+1)`$-breaker.

Proof: The first item is an immediate consequence of the Hall marriage theorem. That theorem states that $`𝒢_D`$ has a perfect matching if and only if there is no set $`B`$ such that $`B`$ has $`m`$ more white vertices than black vertices and there are fewer than $`m`$ edges connecting white vertices of $`B`$ to its complement. A $`(1)`$-cut is clearly such a set, with $`m=1`$. Conversely, given $`B`$ as described above, construct $`B^{}`$ by removing from $`B`$ all of the (at most $`m1`$) white vertices of $`B`$ connected to the complement of $`B`$, and if necessary, some arbitrary additional white vertices (so that $`m1`$ vertices are removed in all). Then $`B^{}`$ is a $`(1)`$-cut.

For the second item, first, it is clear that if $`A`$ is a $`0`$-cut of $`B`$, then all of the edges connecting $`A`$ to its complement will be unused. Conversely, if $`𝒢_D`$ has an unused edge $`e`$, then the graph $`G`$ formed by removing edge $`e`$ and its two vertices from $`𝒢_D`$ will not have any perfect matching. Therefore it will have a $`(1)`$-cut $`A`$ by part 1. The union of $`A`$ and the black vertex of $`e`$ is a thus a $`0`$-cut. (Aside: if $`𝒢_D`$ has a forced edge—i.e., an edge $`e`$ which occurs in every perfect matching of $`𝒢_D`$—then all the edges that share vertices with $`e`$ will be unused.)

The same argument implies the third statement in the case $`k=0`$. For larger $`k`$, if $`𝒢_D`$ has a $`k`$-cut $`A`$, then any subset of $`(k+1)`$ black vertices of $`A`$ and $`(k+1)`$ white vertices of its complement is a $`(k+1)`$-breaker (since the remaining set of vertices in $`A`$ contains more white than black vertices, but there are no edges connecting white vertices of this remaining set with its complement). Conversely, if $`S`$ is a $`(k+1)`$-breaker, then $`𝒢_D\backslash S`$ has a $`(1)`$-cut $`A`$, and the union $`A`$ and the black vertices of $`S`$ is a $`k`$-cut of $`𝒢_D`$. $`\mathrm{}`$

###### Lemma 4.5

$`𝒢_D`$ has no $`k`$-breaker (or, equivalently, no $`(k1)`$-cut) if and only if, for a generic choice of positive weights of the edges of $`𝒢_D`$, the Kastelyn matrix $`K=K(𝒢_D)`$ is $`k`$-non-degenerate.

Proof: The determinant of an $`(nk)\times (nk)`$ minor of the Kastelyn matrix is a polynomial of the edge weights. Clearly, this polynomial will be zero for a given minor precisely when the set of $`k`$ white and $`k`$ black vertices corresponding to rows and columns not in the minor is a $`k`$-breaker. The result follows from the fact that any non-zero polynomial in finitely many real variables is non-zero for a generic choice of inputs. $`\mathrm{}`$

In this paper, we will mainly be interested in whether $`K`$ is $`k`$-degenerate for $`k\{0,1,2\}`$. But we know that whenever $`K`$ is a Kastelyn matrix (of a graph having a perfect matching) it is $`k`$-non-degenerate for $`k=0`$. And assuming $`𝒢_D`$ has no unused edges (which we may always assume throughout, since the perfect matching model will be unchanged if we remove unused edges from $`𝒢_D`$) $`K`$ is generically $`1`$-non-degenerate. We will address the potential failure of $`K`$ to be $`2`$-non-degenerate in a later section.

### 4.2 T-graphs: construction via integration of Kastelyn flow

Let $`𝒢_D`$ be a finite, weighted bipartite planar graph (with positive generic weight function $`\nu `$) with $`n`$ black vertices $`b_1,b_2,\mathrm{},b_n`$ and $`n`$ white vertices $`w_1,w_2,\mathrm{},w_n`$. Suppose $`𝒢_D`$ has a perfect matching and no unused edges. Suppose that $`𝒢_D`$ has no $`1`$-cuts—and hence each of the entries and two-by-two minors of $`K^1`$ is non-zero (i.e., $`K`$ is $`1`$-non-degenerate and $`2`$-non-degenerate).

We will now construct a T-graph corresponding to $`𝒢_D`$ in the case that $`K`$ is $`2`$-non-degenerate.

First, we may think of $`K`$ as describing a linear map from the space $`^W`$ of functions on white vertices to the space $`^B`$ of functions on black vertices. Let $`b_0`$ be a fixed vertex on the outer boundary of $`𝒢_D`$. Suppose that $`𝒢_D`$ has $`m`$ black and $`m`$ white vertices on its outer boundary face. Fix a generic convex $`m+1`$-gon $`Q`$ with edge vectors $`q_0,\mathrm{},q_m`$ in cyclic order (and $`q_0=_{i=1}^mq_i`$). Vertices of $`Q`$ will be the root vertices of $`𝒢_T`$. Suppose that $`A_w^W`$ assumes the values $`q_1,\mathrm{},q_m`$ in cyclic order on the white vertices on the boundary face, and that $`A_w`$ vanishes on all other white vertices of $`𝒢_D`$. Let $`A_b`$ be the function on black vertices which is equal to $`1`$ at $`b_0`$ and $`0`$ everywhere else. Denote by $`\overline{1}`$ the all-ones column vector and by $`\overline{1}^t`$ its transpose. View $`A_b`$ as a column vector and $`A_w`$ as a row vector.

We claim that there is a unique matrix $`\stackrel{~}{K}`$, gauge equivalent to $`K`$, for which $`\stackrel{~}{K}\overline{1}`$ is a non-zero multiple of $`A_b`$ and $`\overline{1}^t\stackrel{~}{K}=A_w`$. The matrix $`\stackrel{~}{K}`$ can be derived explicitly from $`K`$ as follows. Since $`K`$ is invertible, there exists a vector $`f`$ for which $`Kf=A_b`$. Multiplying the $`i`$th column of $`K`$ by the $`i`$th component of $`f`$ (non-zero, because $`K`$ is $`1`$-non-degenerate) produces a $`K^{}`$ for which $`K^{}\overline{1}=A_b`$. Next, there exists a row vector $`g`$ for which $`gK^{}=A_w`$. Multiplying the $`j`$th row of $`K^{}`$ by the $`j`$th component of $`g`$ (also non-zero, since $`(K^{})^1`$ is $`1`$-non-degenerate and nonzero entries of $`A_w`$ are generic) gives the desired $`\stackrel{~}{K}`$.

We may think of $`\stackrel{~}{K}`$ as describing a vector flow ($`2`$-component flow) on $`𝒢_D`$: sending $`\stackrel{~}{K}_{i,j}`$ units of flow from $`b_i`$ to $`w_j`$. The net flow into each non-boundary white vertex and each black vertex (except $`b_0`$) is zero. Now, draw a dotted line from each white vertex on the outer face of $`𝒢_D`$ to infinity, and from $`b_0`$ to infinity, so as to divide the outer face of $`𝒢_D`$ into $`m+1`$ outer faces; take these faces and the interior faces of $`𝒢_D`$ as the vertices of the dual graph $`𝒢_D^{}`$ of $`𝒢_D`$. Then $`\stackrel{~}{K}`$ also describes a dual flow on $`𝒢_D^{}`$ (obtained by rotating each edge ninety degrees counter-clockwise) whose net flow around each non-boundary face of $`𝒢_D^{}`$ is zero; viewed in this light, $`\stackrel{~}{K}`$ is the gradient of a function $`\psi :𝒢_D^{}`$.

Now, we claim that each pair of (complex) components of $`g`$ is linearly independent (as a pair of vectors in $`=^2`$). To see this, let $`a`$ and $`b`$ be basis column vectors, so that $`(K^{})^1(a)`$ and $`(K^{})^1b`$ are columns of the matrix $`(K^{})^1`$. Since the determinants of the two-by-two minors of $`(K^{})^1`$ are non-zero, no complex component of the vector $`z=(K^{})^1a+i(K^{})^1b=(K^{})^1(a+ib)`$ is a real multiple of any other component of that vector (in particular, all of the components of $`z`$ are non-zero). Now $`A_w`$ is a generic linear combination of vectors of the above form $`a+ib`$, so no component of $`g=K^1(A_w)`$ is a real multiple of any other component of $`g`$.

Since $`K^{}`$ is real, all the components of $`\stackrel{~}{K}`$ in a given row are nonzero complex numbers lying on the same line through the origin, and the directions are different in each row.

Now, extend $`\psi `$ linearly to the edges of $`𝒢_D^{}`$, so that $`\psi `$ maps each edge to a line segment. For each black vertex $`b_i`$ of $`𝒢_D`$, corresponding to a black face of $`𝒢_D^{}`$, the $`\psi `$ image of the union of the edges incident to $`b_i`$ is a line segment, whose interior we denote by $`L_i`$; the above argument implies that no two of the $`L_i`$ are parallel.

Here is the main result.

###### Theorem 4.6

If $`K`$ is $`2`$-non-degenerate then the $`L=\{L_1,\mathrm{},L_n\}`$ defined above forms a T-graph with root vertices at vertices of $`Q`$, and $`𝒢_D=𝒢_D(L)`$ (up to gauge equivalence). Moreover, if $`v`$ is a vertex of $`𝒢_D^{}`$, then $`\psi (v)`$ is a vertex of the T-graph; if $`v`$ corresponds to an outer face of $`𝒢_D`$, then $`\psi (v)`$ is a root vertex of the T-graph.

Proof: First, the change in $`\psi `$, as one moves from outer face $`F`$ of $`𝒢_D`$ around a vertex $`v`$ to another outer face, is given by the flow of $`\stackrel{~}{K}`$ into $`v`$, which is given by $`q_i`$, the $`i`$th component of $`A_w`$, whenever $`v`$ is a white vertex $`w_i`$, and zero when $`v`$ is any black vertex besides $`b_0`$. By moving around the polygon in steps, it is clear that (up to an additive constant) $`\psi (F)`$ assumes the values of the vertices of the convex polygon in cyclic order.

Let $`f`$ be an interior vertex of $`𝒢_D^{}`$. We claim that for some black face incident to $`f`$, with vertices $`f_1`$ and $`f_2`$ incident to $`f`$, $`\psi (f_1)\psi (f)`$ and $`\psi (f_2)\psi (f)`$ point in opposite directions. Suppose otherwise. Then $`\stackrel{~}{K}`$ would have to assume opposite signs on the entry corresponding to each such pair of edges $`(f,f_1)`$ and $`(f,f_2)`$. By the definition of a Kastelyn matrix, $`\stackrel{~}{K}`$ has positive sign for an odd (resp., even) number of the edges incident to $`f`$ if the total number of edges is $`0mod4`$ (resp., $`2mod4`$), so this is a contradiction. It follows that $`\psi (f)`$ is an interior vertex of at least one $`L_i`$. In particular, this implies that the endpoint of each $`L_i`$ is either an interior vertex of some $`L_j`$ or a root vertex.

It also implies a maximal principle, i.e., that for any vector $`u`$ in $`^2`$, the function $`\psi _u(x)=(\psi (x),u)`$ (an inner product computed with $`\psi (x)`$ treated as a vector in $`^2`$) has no local maxima or minima at interior faces of $`𝒢_D`$. That is, every interior face $`f`$ (viewed as an interior vertex in $`𝒢_D^{}`$) has neighbors $`f_1`$ and $`f_2`$ satisfying $`\psi _u(f_1)\psi _u(f)\psi _u(f_2)`$. For generic $`u`$ (i.e., any $`u`$ whose slope is not parallel to one of the $`L_i`$’s), the inequality can be made strict.

Now, to show that the $`\{L_i\}`$ form a T-graph, it remains only to show that they do not intersect one another; while proving this, we will also show that $`\psi (𝒢_D^{})`$ partitions the convex polygon $`Q`$ into convex polygons (the white faces). First, the maximal principle immediately implies that $`\psi (𝒢_D^{})`$ lies in $`Q`$. Furthermore, we claim that as one moves $`x`$ clockwise around each a white interior face $`w`$ of $`𝒢_D^{}`$, $`\psi (x)`$ traces out a convex polygon in some fixed orientation (clockwise or counterclockwise; we refer to this direction as the orientation of $`w`$ and denote the polygon by $`\psi (w)`$). If this were not the case, then there would have to be vertices $`f_1,f_2,f_3,f_4`$, in clockwise order around $`w`$ and some generic $`u`$ for which $`\psi _u(f_1)`$ and $`\psi _u(f_3)`$ are less than both of $`\psi _u(f_2)`$ and $`\psi _u(f_4)`$. By the maximal principle, we can find paths in $`p_2`$ and $`p_4`$ in $`𝒢_D^{}`$ from $`f_2`$ and $`f_4`$ to root vertices along which $`\psi _u`$ is strictly increasing and paths $`p_1`$ and $`p_3`$ from $`f_1`$ and $`f_3`$ to root vertices along which $`\psi _u`$ is strictly decreasing. Now, let $`p`$ be a path in $`𝒢_D^{}`$ formed by concatenating $`p_1`$ (reversed), a dotted line from $`f_1`$ to $`f_3`$, and $`p_3`$. This path cannot intersect $`p_2`$ or $`p_4`$ (since $`\psi _u`$ at any point on these two paths is greater than $`\psi _u`$ at any point on $`p_1`$ or $`p_3`$). However, the Jordan curve theorem implies that $`p`$ separates its complement in $`𝒢_D^{}`$ into at least two connected components and that $`f_2`$ and $`f_4`$ (which lie on either side of $`p`$ across the face $`w`$) are in separate components (this remains true even for the graph $`(𝒢_D^Q)^{}`$ formed by adding to $`𝒢_D^{}`$ the edges connecting each cyclically consecutive pair of outer vertices of $`𝒢_D^{}`$). Now, the paths $`p_2`$ and $`p_4`$ both lead to root vertices at which $`\psi _u`$ assumes a larger value than it does at any point along $`p`$, and these points are in the same component of $`(𝒢_D^Q)^{}`$, a contradiction. A similar argument shows that the outer faces $`w`$, joined with this, have this orientation. Another similar argument applies to black faces and shows that as one moves $`x`$ around a black interior face $`b`$ of $`𝒢_D^{}`$, $`\psi (x)`$ traverses the corresponding $`L_i`$ exactly once in each direction.

Next, we argue that all white faces have the same orientation. It is enough to prove that any white faces of $`𝒢_D^{}`$ (vertices of $`𝒢_D`$) $`w_1`$ and $`w_2`$ incident to a common black $`b`$ have the same orientation. Now, as $`x`$ traverses the boundary of the face $`b`$ in $`𝒢_D^{}`$, $`\psi (x)`$ traces out the corresponding $`L_i`$ once in each direction; divide the faces incident to $`b`$ into two categories according to the orientation of the edge shared with $`b`$. Clearly, if these faces do not all have the same orientation, we can find two of them, $`w_1`$ and $`w_2`$ in opposite categories that have opposite orientations. In this case, $`\psi (w_1)`$ and $`\psi (w_2)`$ will lie on the same side of $`b`$; let $`u`$ be vector orthogonal to $`L_i`$; assume without loss of generality that $`\psi _u`$ assumes a larger value on points on $`L_i`$ than on other points of $`w_1,w_2`$. Let $`f_1`$ and $`f_3`$ be the points in $`𝒢_D^{}`$ incident to $`b`$ whose images are the endpoints of $`b`$, and let $`f_2`$ and $`f_4`$ be arbitrary points of $`w_1`$ and $`w_2`$ which do not lie on $`b`$. Let $`p`$ be formed by concatenating a path $`p_1`$ from $`f_1`$ to a root on which $`\psi _u`$ is strictly increasing (reversed), a dotted line from $`f_1`$ to $`f_3`$, and a path $`p_3`$ from $`f_3`$ to a root vertex along which $`\psi _u`$ is strictly increasing; observing that $`f_2`$ and $`f_4`$ are on opposite sides of $`p`$, we derive a contradiction through the Jordan curve argument described above.

Finally, suppose that two of the $`L_i`$ intersect. Then there must be two faces $`w_1`$ and $`w_2`$ for which $`\psi (w_1)`$ and $`\psi (w_2)`$ intersect. The outer boundary of $`(𝒢_D^Q)^{}`$ is mapped with some consistent orientation to $`Q`$. Now, let $`h:Q`$ at $`x`$ be the number of white faces $`\psi (w)`$ which contain $`x`$ in their interiors. It is clear that $`h`$ assumes the value $`1`$ near the boundary. We claim that $`h`$ is equal to one throughout $`Q\backslash \psi (𝒢_D^Q)^{}`$; otherwise, there would be an $`x`$ in the interior of $`Q`$ (and not at the finitely many endpoints of any $`L_i`$ or intersections of pairs of $`L_i`$) on the boundary of regions at which $`h`$ assumes different values. Such an $`x`$ must lie on some $`L_i`$, and it is not hard to see that the two white faces incident to $`x`$ and $`L_i`$ must have opposite orientations. $`\mathrm{}`$

### 4.3 Flat-face degeneracy

Now, suppose that $`K`$ is merely $`1`$-non-degenerate and not necessarily $`2`$-non-degenerate; then we can formally construct $`\psi `$ exactly as above; in this case, however, we cannot rule out that some of the $`L_i`$ may be parallel to one another—and in fact, some of the $`L_i`$ may overlap. However, the same arguments given above still imply that for each white $`w`$, $`\psi (w)`$ is either a convex face with some orientation (as described above) or a line segment traversed once in each direction (like the black faces). In the latter case, we say $`\psi (w)`$ is a degenerate face. In the presence of degenerate faces, we will consider $`\psi (w)`$ and $`\psi (b)`$ to be incident to one another along an edge if and only if $`w`$ and $`b`$ are adjacent vertices in $`𝒢_D^{}`$.

It is clear that if a white vertex $`w`$ is degenerate, then $`\psi (b)`$ is parallel to $`\psi (w)`$ for each black $`b`$ adjacent to $`w`$. A maximal component of the subgraph of $`𝒢_D^{}`$ consisting of vertices on which $`\psi `$ is parallel to a given line is called a parallel component of $`𝒢_D^{}`$. Clearly, the neighbor set of any white vertex in a parallel component is also in the parallel component.

An extreme point of a degenerate face $`w`$ is a vertex $`f`$ incident to $`w`$ for which $`\psi (f)`$ is an endpoint of $`\psi (w)`$. The union of $`\psi `$-images of a parallel component is a segment which we call an extended complete edge. Now observe the following.

###### Lemma 4.7

Each parallel component $`P`$ is a $`1`$-cut.

Proof: Observe that every $`f`$ which is an interior vertex of a black edge of $`𝒢_D^{}`$ in a parallel cluster is the extreme vertex for the same number of black and white faces of $`𝒢_D^{}`$. The endpoints of the extended complete edge are extreme points of one more black vertex than white vertices. Since every face has exactly two extreme vertices, the result follows. $`\mathrm{}`$

Similar arguments to those given in the proof of Theorem 4.6 imply that as $`x`$ traverses the outside of a parallel component, $`\psi (x)`$ traverses the outside of the extended complete edge exactly once in each direction. Similar arguments to those of Theorem 4.6 imply that the extended complete edges form a T-graph. We say that $`L=\{L_i\}`$ forms a T-graph with overlaps if $`L_i`$ satisfies all of the T-graph conditions except that parallel pairs of $`L_i`$ are allowed to intersect (overlap) one another. The above analysis implies the following:

###### Theorem 4.8

Theorem 4.6 still holds if $`K`$ is merely $`1`$-non-degenerate and not necessarily $`2`$-non-degenerate—except that in this case, some of the white faces may be degenerate (and so the T-graph may have overlaps). Theorem 3.4 still applies to T-graphs with overlaps.

Even though some of the white faces are flat in the overlapping T-graph $`𝒢_T`$, we can define a dual to the overlapping T-graph, containing these faces, using the graph structure of $`𝒢_D`$. After doing this, all of the arguments in the proof of Theorem 3.4 apply as before, so we still have a martingale on the T-graph and have a measure preserving correspondence between spanning forests and perfect matchings.

Recall that in any perfect matching, there is always exactly one edge connecting a given $`1`$-cut to its complement, and that edge contains a black vertex of the $`1`$-cut. It is perhaps not surprising that when we form the T-graph, $`1`$-cuts, in some sense, play the same role as single black vertices. If we had simply replaced all $`1`$-cuts in our original graph with single black vertices, then, for a generic choice of weights, the T-graph would not have any degenerate white faces.

### 4.4 Extending the correspondence to degenerate weighted graphs

Recall from Lemma 4.5 that if we remove the unused edges from $`𝒢_D`$, then the Kastelyn matrix for $`𝒢_D`$ is $`1`$-non-degenerate (and hence Theorems 3.4 4.8 apply) for a generic choice of weight functions $`\nu `$. Suppose, however, that the Kastelyn matrix for $`𝒢_D`$ is not $`1`$-non-degenerate for a particular choice of weight function $`\nu `$. Then we would like to take a generic sequence of weights $`\nu _i`$ converging to $`\nu `$, look at the limit (or some subsequential limit) of the corresponding T-graphs, and show that the measure-preserving correspondence described in Theorem 3.4 still holds for the limiting object. The problem is that, as Figure 1 makes clear, the limit of a sequence of T-graphs need not be a T-graph at all; in fact, some of the edge segments and faces may shrink to single points.

For practical computational applications, it may be sufficient to have the correspondence between dimers and spanning forests for a generic choice of weights. But a word of caution is in order. Consider the dimer model whose T-graph is given by the right diagram in Figure 1; if weights $`\nu _i`$ tend to a limit $`\nu `$ in such a way that the T-graphs have the graph on the left as a limit, then the shrinking small triangle in the center of the diagram will become a “trap” for the random walk on the T-graph, in that the expected amount of time that a walk spends on these three vertices before exiting towards a root vertex tends to infinity; sampling algorithms that rely on random walks will perform poorly for weights approximating $`\nu `$. In this case, however, one can simplify the limiting problem by reducing the three vertices in the small triangle at the center to single vertex. The probability tends to one that only one of the “long” directed edges (i.e., edges whose lengths are not tending to zero) extending outward from these three vertices will appear in a random tree; given a spanning tree of the “reduced” graph, it is possible to work out which “short” edges appear in the graph. The details of this and more general versions of this reduction are left to the reader.

## 5 Periodic and almost periodic T-graphs

### 5.1 Definitions for almost periodic T-graphs

In this section, we prove some results about T-graphs which are motivated by the study of ergodic Gibbs measures on tilings of infinite periodic planar graphs. More on this subject can be found in , who cite the results of this section. Our first aim here is to construct from periodic bipartite planar graphs (and under certain conditions on the weights) infinite T-graphs with a property called “almost periodicity.”

Let $`𝒢_D`$ be embedded in the torus $`^2/^2`$ and let $`𝒢_D^{\mathrm{}}`$ be the doubly periodic lift to $`^2`$ (we assume that $`𝒢_D^{\mathrm{}}`$ is connected). As before, assume that $`𝒢_D`$ has $`n`$ white and $`n`$ black vertices. Denote by $`v_{j,k}`$ the vertex of $`𝒢_D^{\mathrm{}}`$ which lies in the square $`[j,j+1)\times [k,k+1)`$ and whose projection to the torus is the vertex $`v𝒢_D`$. For the sake of simplicity we will assume throughout this section that $`𝒢_D`$ has no unused edges and that it has generic weights. The non-generic weight case requires a slightly finer analysis which we choose not to go into here. See however .

A function $`f`$ on the vertices of $`𝒢_D`$ is $`(\alpha ,\beta )`$-periodic if $`f(v_{j+x,k+y})=\alpha ^x\beta ^yf(v_{j,k})`$ for all $`(v_{j,k})𝒢_D^{\mathrm{}}`$. Say $`f`$ is almost periodic if it is $`(\alpha ,\beta )`$-periodic and $`\alpha `$ and $`\beta `$ have modulus one (but are not necessarily roots of unity). In this case, we write $`\alpha =e^{2\pi ia}`$ and $`\beta =e^{2\pi ib}`$. If $`a`$ and $`b`$ are rational, then $`f`$ is doubly periodic with some period.

For a fixed $`(\alpha ,\beta )`$ the linear space of $`(\alpha ,\beta )`$-periodic functions is $`2n`$-dimensional and is parametrized by the space of functions on one period of $`𝒢_D^{\mathrm{}}`$—which we can represent as a single copy of $`𝒢_D`$. It has a natural basis consisting of functions $`\delta _v`$ whose value is $`1`$ at $`v[0,1)^2`$ and zero at other vertices in the fundamental domain. Let $`K`$ be a Kastelyn matrix for $`𝒢_D`$ and $`K^{\mathrm{}}`$ an infinite-dimensional Kasteleyn matrix for $`𝒢_D^{\mathrm{}}`$ which is a lift of $`K`$. We can think of $`K^{\mathrm{}}`$ as a linear function from the set of functions on the black vertices of $`𝒢_D^{\mathrm{}}`$ to functions on the white vertices of $`𝒢_D^{\mathrm{}}`$. Since this function maps $`(\alpha ,\beta )`$-periodic functions to $`(\alpha ,\beta )`$-periodic functions, it induces a linear map from the $`n`$-dimensional space of functions on the black vertices of $`𝒢_D`$ to the $`n`$-dimensional space of functions on white vertices of $`𝒢_D`$. Denote by $`K_{\alpha ,\beta }`$ the matrix of this linear map in the basis $`\{\delta _v\}`$.

The determinant $`detK_{\alpha ,\beta }`$ is a polynomial function of $`\alpha `$ and $`\beta `$; in particular for certain $`(\alpha ,\beta )`$ (corresponding to zeros of this polynomial function) the matrix $`K_{\alpha ,\beta }`$ has a non-trivial null space, and hence we can find $`(\alpha ,\beta )`$-periodic functions $`f`$ and $`g`$ satisfying $`K^{\mathrm{}}f=0`$ and $`gK^{\mathrm{}}=0`$. If the polynomial $`detK_{\alpha ,\beta }`$ happens to have a zero $`(\alpha ,\beta )`$ that lies on the unit torus of complex variable pairs that both have modulus one, then $`f`$ and $`g`$ are almost periodic. If, furthermore, $`f`$ and $`g`$ happen to be nowhere zero, then we can define an infinite T-graph as follows. First, observe that the function $`\stackrel{~}{K}_1^{\mathrm{}}(vw)=f(v)g(w)K^{\mathrm{}}(v,w)`$ on edges $`vw`$ of $`𝒢_D^{\mathrm{}}`$ is a nowhere zero flow. The dual of this flow is the gradient of a function $`\psi _1`$ on $`𝒢_D^{}`$. Similarly the dual of $`\stackrel{~}{K}_2^{\mathrm{}}(vw)=f(v)\overline{g(w)}K^{\mathrm{}}(v,w)`$ is the gradient of a function $`\psi _2`$ on $`𝒢_D^{}`$ (where $`\overline{g}`$ denotes the complex conjugate of $`g`$). We may assume (multiplying $`g(w)`$ by a generic modulus one complex number if necessary) that $`g(w)+\overline{g(w)}=2\mathrm{R}\mathrm{e}g(w)`$ is also nowhere zero. Then we can think of $`\stackrel{~}{K}=\stackrel{~}{K}_1+\stackrel{~}{K}_2`$ as an infinite Kastelyn matrix and $`\psi =\psi _1+\psi _2`$ as the corresponding T-graph. We will call a mapping $`\psi `$ from $`(𝒢_D^{\mathrm{}})^{}`$ to $`^2`$, constructed in this way, an almost periodic T-graph mapping. See Figure 5.

We remark that, given a fixed $`\nu `$, the number of $`\alpha ,\beta `$ on the unit torus for which $`detK_{\alpha ,\beta }=0`$ also plays a fundamental role in , where it is shown that the minimal specific free energy ergodic Gibbs measure on perfect matchings of the infinite weighted graph $`𝒢_D^{\mathrm{}}`$ is smooth if the corresponding polynomial $`K_{\alpha ,\beta }`$ polynomial has $`0`$ roots on the unit torus and rough if it has $`2`$ roots (necessarily complex conjugates) on the unit torus (in the non-generic case of a single root, it is rough only when $`\frac{d}{d\alpha }detK_{\alpha ,\beta }=\frac{d}{d\beta }detK_{\alpha ,\beta }=0`$). The terms “smooth” and “rough” come from the statistical physics literature and are defined in . The main goal of this section is to prove that when the choice of weights is generic, the number of modulus-one values of $`(\alpha ,\beta )`$ that are roots of $`detK_{\alpha ,\beta }`$ always belongs to the set $`\{0,2\}`$.

### 5.2 Generic points on the variety of almost periodic T-graphs

Write $`_+`$ for the set of strictly positive real numbers, $`_+`$ for the set of non-zero complex numbers, and write $`^k`$ for $`k`$-dimensional complex projective space. Suppose that $`|V|=2n`$, and define a variety $`X_+^{|E|}\times _+^2\times ^{n1}`$ by:

$$X=\{(\nu ,\alpha ,\beta ,f):K_{\alpha ,\beta }f=0\}$$

Here $`f`$ is an element in $`^{n1}`$, which is a one-dimensional subspace of $`^n`$, and by $`K_{\alpha ,\beta }f=0`$ we mean that this subspace lies in the null space of $`K_{\alpha ,\beta }`$. By abuse of notation, if $`f`$ is a non-zero function on the black vertices of $`𝒢_D`$, we will also use $`f`$ to denote the element of $`^{n1}`$ given by the linear span of $`f`$. Denote by $`\stackrel{~}{X}`$ the subset of $`X`$ consisting of points for which $`|\alpha |=|\beta |=1`$. Denote by $`\mathrm{Adj}(K_{\alpha ,\beta })`$ the adjugate matrix of $`K_{\alpha ,\beta }`$, whose entries are the $`(n1)\times (n1)`$ minors of $`K_{\alpha ,\beta }`$ (so that $`K_{\alpha ,\beta }\mathrm{Adj}(K_{\alpha ,\beta })=detK_{\alpha ,\beta }`$). It is easily seen that $`\mathrm{Adj}(K_{\alpha ,\beta })`$ is identically equal to zero if and only if the rank of $`K_{\alpha ,\beta }`$ is less than $`n1`$; and if the rank of $`\mathrm{Adj}(K_{\alpha ,\beta })`$ is exactly $`n1`$, then at least one column of $`\mathrm{Adj}(K_{\alpha ,\beta })`$ is a non-zero vector whose span is the null space of $`\mathrm{Adj}(K_{\alpha ,\beta })`$. The following is the main result of this section:

###### Theorem 5.1

The variety $`\stackrel{~}{X}`$ is irreducible. For a generic choice of $`\nu `$, there are either zero or two quadruples $`(\nu ,\alpha ,\beta ,f)`$ in $`X`$. When the latter is the case and $`\nu `$ is generic, then the corresponding $`\alpha ,\beta ,f`$ are such that $`\mathrm{Adj}(K_{\alpha ,\beta })`$ has rank $`n1`$, all of its coordinates are non-zero, and $`f`$ is given by any column of the (rank one) matrix $`\mathrm{Adj}(K_{\alpha ,\beta })`$.

Let us say a word about the significance of this theorem to T-graph classification before we prove it. By obvious symmetry, Theorem 5.1 implies that that for generic $`\nu `$, there are either zero or exactly two quintuples $`(\nu ,\alpha ,\beta ,f,g)`$ with $`gK_{\alpha ,\beta }=0`$ and $`fK_{\alpha ,\beta }`$. Recall that our almost periodic T-graphs were defined to have gradient given by $`\stackrel{~}{K}^{\mathrm{}}(vw)=2f(v)\mathrm{Re}(g(w))K^{\mathrm{}}(v,w)`$. Since $`f`$ and $`g`$ are uniquely determined up to complex conjugacy and multiplication by a constant factor, this implies that the almost periodic T-graph is completely determined up to rotations (which arise from multiplying $`f`$ by a modulus one constant), constant rescalings (which arise from multiplying either $`g`$ or $`f`$ by a real constant), reflection (which comes from complex conjugacy), translations of the image space (which arise from the fact that $`\stackrel{~}{K}^{\mathrm{}}`$ only determines the T-graph mapping up to an additive constant) and “translation of the domain, or a limit of such translations.” To explain the last symmetry, note that multiplying both $`f`$ and $`g`$ by $`\alpha ^m\beta ^n`$ is equivalent to composing the T-graph mapping with translation of the domain by $`(m,n)`$. If one of $`\alpha ,\beta `$ is irrational, then we can achieve any modulus one number as a limit of numbers of the form $`\alpha ^m\beta ^n`$. We summarize these observations informally by saying that “the almost periodic T-graph mapping corresponding to $`\nu `$ is unique up to affine orthogonal transformations of the image and translations of the domain.” We say two T-graphs are equivalent if one can be obtained from the other via a symmetry of this sort. Note, of course, that if $`\alpha `$ and $`\beta `$ are both rational, then multiplying $`f`$ and $`g`$ by a modulus one number is not necessarily the same as a domain translation, or even a limit of such translations. In this case, there is a one parameter family of T-graph equivalency classes.

We will now prove Theorem 5.1 in stages, beginning with the following lemma. First, denote by $`X^{}`$ the projection of $`X`$ onto its first three coordinates $`(\nu ,\alpha ,\beta )`$; i.e., $`X^{}`$ is the zero set of the polynomial $`P(\nu ,\alpha ,\beta )=detK_{\alpha ,\beta }`$.

###### Lemma 5.2

The variety $`X^{}`$ is irreducible. Moreover, for a generic point $`(\nu ,\alpha ,\beta )`$ on $`X^{}`$, the matrix $`\mathrm{Adj}(K_{\alpha ,\beta })`$ has no zero entries, and the $`f`$ for which $`(\nu ,\alpha ,\beta ,f)X`$ is unique.

Proof: Clearly, $`P`$ is affine linear as a function of $`\nu (e)`$, that is $`P=\nu (e)P_e+P_e^{},`$, where $`P_e`$ and $`P_e^{}`$ do not involve $`\nu (e)`$. If we could write $`P=P_1P_2`$, then each $`\nu (e)`$ must occur in either $`P_1`$ or $`P_2`$, but not both. Since the multiplicity of the $`\nu (e)`$ terms determine the multiplicity of $`\alpha `$ and $`\beta `$ in each monomial, this implies that there is no cancellation when multiplying out $`P_1`$ times $`P_2`$ (i.e., there are no monomials that can represented as a product of a monomial in $`P_1`$ and a monomial in $`P_2`$ in two different ways). Thus, each monomial in $`P_1`$ times a monomial of $`P_2`$ corresponds to a matching. Let $`E_1,E_2`$ be the set of edges represented in $`P_1,P_2`$, respectively, and $`V_1,V_2`$ their vertices. If an edge $`e`$ connected a vertex $`v_1`$ of $`V_1`$ to a vertex $`v_2`$ of $`V_2`$, then its weight could not occur in either $`P_1`$ or $`P_2`$, since if it occurred in a monomial of, say, $`P_1`$, then the product of that monomial with a monomial of $`P_2`$ that included a factor of $`\nu (e^{})`$ with $`e^{}`$ incident to $`v_2`$ (such a monomial exists by definition) would not correspond to a matching, since it would involve two edges incident to $`v_2`$. Thus $`e`$ must be unused, a contradiction. Thus, if $`P=P_1P_2`$, then one of the $`P_i`$—say, $`P_2`$—must be a function of $`\alpha `$ and $`\beta `$ alone. Since each combination of edge weights corresponding to a matching occurs in exactly one monomial of $`P`$, we conclude that $`P_2`$ is a monomial in $`\alpha `$ and $`\beta `$.

Furthermore $`P`$ is irreducible when considered as a polynomial in both the edge weights and $`\alpha ,\beta `$, except for a monomial factor in $`\alpha `$ and $`\beta `$. That is, if $`P=P_1(\nu ,\alpha ,\beta )P_2(\nu ,\alpha ,\beta )`$ then one of the $`P_i`$ consists of a single monomial in $`\alpha `$ and $`\beta `$. To see this, note that by the previous result, we may assume without loss of generality that $`P_2`$ is a polynomial in $`\alpha ,\beta `$ alone; and since we are assuming $`\alpha 0,\beta 0`$, the variety is not changed if we divide out by this term so that $`P`$ is an irreducible polynomial.

Fix an edge $`e`$ and consider the polynomial $`P_e`$ as defined above. Since $`P`$ is irreducible and $`e`$ occurs in a proper subset of the set of all matchings, the zero set of $`\nu (e)P(e)`$, intersected with $`X^{}`$, forms a proper subvariety of $`X^{}`$. In other words, on a generic subset of $`X^{}`$, none of the entries of $`\mathrm{Adj}(K_{\alpha ,\beta })`$ corresponding to an edge in $`𝒢_D`$ are zero. Since $`\mathrm{Adj}(K_{\alpha ,\beta })`$ has rank at most one, and every row and column has a non-zero entry, we conclude that every entry of $`\mathrm{Adj}(K_{\alpha ,\beta })`$ is non-zero and $`f`$ is the span of any column of $`\mathrm{Adj}(K_{\alpha ,\beta })`$. $`\mathrm{}`$

###### Lemma 5.3

For a generic choice of weights $`\nu `$, every pair $`\alpha ,\beta `$ for which $`(\nu ,\alpha ,\beta )X`$ is such that $`\mathrm{Adj}(K_{\alpha ,\beta })`$ has no zero entries, and the $`f`$ for which $`(\nu ,\alpha ,\beta ,f)X`$ is unique.

Proof: Lemma 5.2 implies that for generic edge weights $`\nu `$, $`P`$ and $`P_e`$ have no common factor as functions of $`\alpha `$ and $`\beta `$ except for monomial factors. To see this, by irreducibility note that there exist polynomials $`Q_1=Q_1(\alpha ,\beta ,w)`$ and $`Q_2=Q_2(\alpha ,\beta ,w)`$ such that $`PQ_1+P_eQ_2=Q(\alpha ,w)`$ where $`Q`$ is a nonzero polynomial depending only on $`\alpha `$ and the weights $`w`$, not on $`\beta `$. Similarly there exist $`Q_3,Q_4`$ such that $`PQ_3+P_eQ_4=Q^{}(\beta ,w)`$ where $`Q^{}`$ is a nonzero polynomial independent of $`\alpha `$. Plugging in generic values for $`w`$, $`Q`$ and $`Q^{}`$ will still be nonzero, but any common factor of $`P`$ and $`P_e`$ is a common factor of $`Q`$ and $`Q^{}`$ which is impossible. So $`P`$ and $`P_e`$ have no common factor for generic $`w`$.

Therefore, when $`\nu `$ is fixed generically, by Bezout’s theorem $`P`$ and $`P_e`$—viewed as polynomials in $`\alpha `$ and $`\beta `$—have a finite number of common zeros. By genericity none of these zeros lies on the unit torus (since for any positive real $`x`$, we can choose $`\nu _x`$ so that $`P(\nu ,\alpha ,\beta )=P_{\nu _x,x\alpha ,x\beta }`$; and replacing $`\nu `$ with such a $`\nu _x`$, for a generic choice of $`x`$, preserves the genericity of the weights). $`\mathrm{}`$

###### Lemma 5.4

Any almost periodic T-graph mapping $`\psi `$ is unbounded as a function of $`(𝒢_D^{\mathrm{}})^{}`$. Moreover if $`u`$ is any vector in $`^2\backslash \{0\}`$, then $`(\psi ,u)`$ is unbounded if it is not identically equal to a constant (in which case $`\psi `$ is degenerate—i.e., its image is contained in a line).

Proof: Suppose that $`f`$ is $`(\alpha ,\beta )`$-periodic and $`g`$ is $`(\gamma ,\delta )`$-periodic with $`\gamma =e^{2\pi ic}`$ and $`\delta =e^{2\pi id}`$. Then $`\stackrel{~}{K}_1^{\mathrm{}}(v_{j,k},w_{j+\mathrm{},k+m})`$ is a function of $`\mathrm{},m`$ whose real and imaginary parts can both be written in the form $`\mathrm{cos}(a\mathrm{}+bm+x)\mathrm{cos}(c\mathrm{}+dm+y)`$ times a constant, for some $`x`$ and $`y`$.

If $`\psi `$ were bounded on $`𝒢_D^{}`$, then the corresponding martingale on the T-graph would almost surely converge (by the martingale convergence theorem), and there would thus have to be a path of vertices $`v_1,v_2,\mathrm{}`$ for which $`\psi (v_i)`$ converges to a constant. We claim that this is impossible. It is enough to show that for some $`ϵ`$, the set of edges $`(vw)^{}`$ for which $`0<\stackrel{~}{K}^{\mathrm{}}(v,w)<ϵ`$ has no infinite cluster. For some $`N>|𝒢_D|`$, we can always find $`ϵ`$ small enough so that the distance between any two clusters of $`(\mathrm{},m)^2`$ (viewed as points in $`^2`$) on which $`0<\mathrm{cos}(a\mathrm{}+bm+x)<ϵ^{1/2}`$ is at least $`2N`$ times the diameter of the largest such cluster, and similarly for clusters on which $`0<\mathrm{cos}(c\mathrm{}+dm+y)<ϵ^{1/2}`$. (This is trivial if $`a`$ and $`b`$ are rational, since the function is periodic in that case; if they are irrational, then we can find $`ϵ_0`$ for which there is no integer pair $`(n_1,n_2)`$ for which $`n_1a+n_2b`$ is less than $`ϵ_0`$ (modulo $`2\pi `$) and $`|n_1+n_2|2N`$. Choose $`ϵ_0`$ small enough that there can’t be two values differing by $`ϵ_0`$ (modulo $`2\pi `$) with cosines $`ϵ`$ apart.) Now, it is clear that the largest cluster of $`\mathrm{},m`$ on which even one of these statements holds is at most $`2N`$; since the gradient of $`\psi `$ has norm at least $`ϵ`$ when neither statement holds, we conclude that $`\psi `$ cannot be bounded.

The same argument shows that there cannot exist a non-zero vector $`u^2`$ for which the inner product $`(\psi (v),u)`$ is bounded as a function of $`v`$, unless $`(\psi (v),u)`$ is constant. $`\mathrm{}`$

###### Lemma 5.5

If $`\nu `$ is generic, then the maximum number of linearly independent, almost periodic solutions to $`K^{\mathrm{}}f=0`$ (or similarly, solutions to $`gK^{\mathrm{}}=0`$) is two. If there are two solutions, which are $`(\alpha ,\beta )`$\- and $`(\gamma ,\delta )`$-periodic, then $`\alpha =\overline{\gamma }`$ and $`\beta =\overline{\delta }`$.

Proof: For each $`\alpha `$ and $`\beta `$, the left null space of $`K_{\alpha ,\beta }`$ has the same dimension as the right null space. Now, suppose that $`f`$ is $`\alpha ,\beta `$-periodic and $`g`$ is $`\gamma ,\delta `$-periodic with $`\gamma =e^{2\pi ic}`$ and $`\delta =e^{2\pi id}`$. Then as in the proof of Lemma 5.4, $`\stackrel{~}{K}^{\mathrm{}}(v_{j,k},w_{j+\mathrm{},k+m})`$ is a function of $`\mathrm{},m`$ whose real and imaginary parts can both be written in the form $`\mathrm{cos}(a\mathrm{}+bm+x)\mathrm{cos}(c\mathrm{}+dm+y)`$ times a constant, for some $`x`$ and $`y`$. Let $`S`$ be a cycle in $`𝒢_D^{}`$; if we lift it to $`(𝒢_D^{\mathrm{}})^{}`$, then its endpoints are its starting points plus an integer pair, $`(n_1,n_2)`$. Now, we would like to determine the asymptotics of $`\psi _1`$ and $`\psi _2`$ (whose derivative is the dual of $`\stackrel{~}{K}^{\mathrm{}}`$) along $`S^{\mathrm{}}`$ (a periodic lifting of $`S`$ to $`𝒢_D^{\mathrm{}}`$). Expanding the cosines in exponentials, this involves adding up $`|S|`$ separate sequences (functions of $`\mathrm{}`$) of the form:

$$\underset{\mathrm{}=1}{\overset{n_1}{}}e^{2\pi i[(x+\mathrm{}a)\pm (y+\mathrm{}c)]}$$

and $`|S|`$ sequences of the corresponding form for $`m`$.

Clearly, $`\psi `$ will remain bounded independently of $`x`$ and $`y`$, provided $`a\pm cmod2\pi `$ and $`b\pm dmod2\pi `$. In fact we must take the same sign for both equalities: unless $`(a,b)=\pm (c,d)mod2\pi `$ it is possible to find an independent pair of integer vectors $`(m_1,n_1)`$ and $`(m_2,n_2)`$ for which $`am_1+bn_1\pm (cm_1+dn_1)mod2\pi `$ and similarly $`am_2+bn_2\pm (cm_2+dm_2)mod2\pi `$. Taking $`S_1`$ and $`S_2`$ to be corresponding paths, we may deduce that $`\psi `$ is bounded unless $`(\alpha ,\beta )`$ and $`(\gamma ,\delta )`$ are either equal to one another or conjugates; by Lemma 5.4 $`(\alpha ,\beta )`$ and $`(\gamma ,\delta )`$ are either equal to one another or conjugates.

Now suppose we have $`(a,b)=\pm (c,d)`$. Then for the sums corresponding to steps in $`S`$,

$$\underset{\mathrm{}=1}{\overset{n_1}{}}\mathrm{cos}(x+\mathrm{}a)\mathrm{cos}(y\pm \mathrm{}a)$$

is approximately linear as a function of $`n_1`$, that is, equal to a linear function plus a bounded function. If there were three linearly independent solutions $`f_1,f_2,f_3`$ to $`Kf=0`$, and $`\psi _1,\psi _2,\psi _3`$ are formed using $`g`$ and $`f_1,f_2,f_3`$, then a linear combination of the $`\psi _1,\psi _2,\psi _3`$ would be approximately the linear function zero (i.e., bounded), a contradiction, by Lemma 5.4.

Finally, since it is clear that $`(\alpha ,\beta )`$ is not real (i.e., not equal to $`\pm 1`$) for a generic choice of $`\nu `$, so any almost periodic $`f`$ or $`g`$ will be a strictly non-real function, that is, linearly independent from its complex conjugate, which is also a zero of $`K^{\mathrm{}}`$. $`\mathrm{}`$

Now, Theorem 5.1 now follows immediately from Lemma 5.3 and Lemma 5.5.


format: text

text:
# Transverse laser modes in Bose-Einstein condensates

## I Introduction

Bose-Einstein condensates (BECs) are the matter-wave equivalent of lasers Rolston and Phillips (2002): all the atoms in a BEC are in the same quantum state, just like all the photons in a laser beam. While in the creation of BECs this property is usually ensured by the fundamental properties of very cold bosons, in a laser it is due to the longitudinal properties of the laser resonator Siegman (1986a). Just like the number of photons can be coherently amplified in a laser, the number of atoms can be coherently amplified in a BEC Inouye et al. (1999); andYoichi Suzuki et al. (1999); Chikkatur et al. (2002).

Laser resonators also have an effect on the transverse structure of laser light. The origin of this transverse structure has a huge literature devoted to it (for an overview see, for example, references Siegman (1986b, 2000)), and a good understanding and control has proved interesting (see, for example, the discovery of fractal modes Karman et al. (1999)) as well as useful. For example, the standard families of laser modes, Hermite-Gaussian (HG) and Laguerre-Gaussian (LG) modes (figure 1), have elegant mathematical properties (for example, they are structurally stable, i.e. they do not change shape on propagation, and form complete orthogonal sets of modes), and LG modes, because of their central vortex of arbitrary topological charge, are one of the most popular choices for optical experiments with optical vortices. Most importantly, however, certain ’stable’ resonators keep the light in the proximity of the optical axis – transversally, they trap the light.

We examine here – in the limit of the Gross-Pitaevskii equation – a process in 2-dimensional BECs that is analogous to the formation of transverse laser modes: periodic focussing and spatial filtering. We believe this could be achieved experimentally with a periodic series of light pulses. We examine this scenario for BECs in a quadratic trap and untrapped BECs. We demonstrate the emergence of HG-like modes, and convert these into LG-like modes using the equivalent of the Gouy phase shift. Our main concern, however, is the question if a series of light pulses could act as a novel type of trap for BECs.

## II Eigenmode selection in laser resonators

Figure 2a sketches one round trip of a light pulse (or alternatively a ’slice’ of a cw light beam) through a standard laser resonator. Most importantly, the light pulse is reflected back by the two mirrors facing each other, so that after one round trip, which involves reflecting off each mirror once, the light pulse is back in the same plane where it started. One round trip is much more complicated than just some changes in propagation direction: as the mirrors are curved, each mirror reflection also focusses the light. In addition, localised loss occurs in one or several planes, for example through apertures or specks of dust on mirrors. Some light beams – the resonator’s eigenmodes – are unchanged (apart from a uniform change in intensity or phase) after one round trip through a resonator. In the case of geometrically stable resonators, which we consider here, the eigenmodes can be divided into families (like the Hermite-Gaussian (HG) modes and the Laguerre-Gaussian (LG) modes), whereby each family forms a complete orthogonal set, i.e. every light beam can, for example, be described as a superposition of HG modes. As already mentioned, the HG and LG modes can take on very recognisable shapes and have interesting features like high-charge vortices (see figure 1).

Experimentally, a pure resonator eigenmode is created in a laser by making that eigenmode the lowest-loss eigenmode, i.e. by ensuring the round-trip loss of all other eigenmodes is higher than that of the desired eigenmode. This can be done, for example, by inserting absorbing cross-wires into the resonator at positions where the desired eigenmode is darker than the competing eigenmodes. For example, an absorbing wire in the central horizontal dark line of the $`\mathrm{HG}_{2,1}`$ mode shown in figure 1 would not significantly increase that eigenmode’s round-trip loss, but it would increase that of the $`\mathrm{HG}_{2,0}`$ mode. The fraction of the power in the undesired eigenmodes then falls of exponentially with round trip number, after a few round trips leaving only the pure lowest-loss eigenmode.

## III Creation of Hermite-Gaussian-like modes in BECs

As far as transverse eigenmode selection is concerned, a resonator can be seen as a series of lenses separated by the length of the resonator (figure 2b). If the focal lengths of the lenses match those of the resonator’s mirrors, and if the important localised loss is the same, then an infinitely long lens-series equivalent of a resonator has the same eigenmodes Siegman (1986a). Such an infinitely long lens-series equivalent of a resonator represents infinitely many round trips. On the other hand, eigenmode selection mostly happens during the first few round trips through the resonator, which can be represented by a few lenses. We examine here the BEC analog of such a series of lenses.

The BEC analog of an optical resonator’s lens-series equivalent can consist of repetitions of lens pulses (focal time $`f`$) and absorption events (figure 2c; absorption events are not shown). The delay between two repetitions, $`L`$, corresponds to the length of the resonator. We refer to such a configuration as a light-pulse resonator. We restrict ourselves to light-pulse resonators in which the absorption events always follows immediately after the lens pulse.

All the pictures of BECs in light-pulse resonators shown in this paper (with the exception of two frames in figure 7) are snapshots taken half-time between two lens pulses, i.e. a time $`L/2`$ after the previous lens pulse. We refer to the sequence of events acting on the BEC between $`L/2`$ after the previous lens pulse and $`L/2`$ after the next lens pulse – time evolution over a time $`L/2`$, interaction with a lens pulse, absorption event, and another time evolution through $`L/2`$ – as one period of the resonator.

We simulate time evolution according to the time-dependent Gross-Pitaevskii equation Pethick and Smith (2002), which we write in the form Caradoc-Davies (2000)

$$i\mathrm{}\frac{\psi (𝐫,t)}{t}=\left[\frac{\mathrm{}^2}{2m}^2+\frac{1}{2}m\omega ^2r^2+V_e(𝐫,t)+g|\psi (𝐫,t)|^2\right]\psi (𝐫,t),$$
(1)
where $`m`$ is the mass of each atom, $`\omega `$ is the trap frequency, $`V_e`$ is an external potential, and $`g`$ is the non-linear coefficient, which is given by

$$g=4\pi N\frac{a}{d}\frac{\mathrm{}^2}{m}.$$
(2)
$`d`$ is the thickness of the BEC in the third dimension (the $`z`$ direction), which needs to be very small for the BEC to behave 2-dimensionally. This is usually ensured by tight $`z`$ confinement by a harmonic trap that satisfies the condition $`\mu <\mathrm{}\omega _z`$, where $`\mu `$ is the chemical potential. Note that $`g`$ depends not only on $`m`$ and $`a`$, the s-wave scattering length, but also on the number of atoms, $`N`$, in the BEC. As the number of particles is contained in the parameter $`g`$, which is very convenient for the purposes of this paper, the density is normalised according to

$$|\psi (𝐫,t)|^2𝑑𝐫=1.$$
(3)
In our computer model we represent the BEC wave function on a square area of $`16\times 16`$ dimensionless units by a $`128\times 128`$ array of double-precision complex numbers. The dimensionless variables for position and time, $`𝐫^{}`$ and $`t^{}`$, are related to the corresponding variables with dimensions, $`𝐫`$ and $`t`$, through the equations

$$𝐫^{}=\left(\frac{2m\omega }{\mathrm{}}\right)^{\frac{1}{2}}𝐫$$
(4)
and

$$t^{}=\omega t.$$
(5)
We solve the Gross-Pitaevskii equation with a fourth-order Runge-Kutta method (a detailed description can be found in ref. Caradoc-Davies (2000)).

We model the effect of a lens pulse by locally altering the phase of the wave function in the same way in which a lens (or a hologram of a lens) would alter the phase of passing light Goodman (1968). In principle (although it has not been demonstrated for the particular phase profile of a lens), this can be achieved experimentally using an off-resonant laser pulse with an intensity profile proportional to the desired local phase change, whose electric field then – through the AC Stark effect – alters the local phase of the BEC. This ’phase imprinting’ method Dobrek et al. (1999); Denschlag et al. (2000) is analogous to optical phase holography. Interestingly, the time after which the BEC comes to a focus after interaction with such a lens pulse is not what one might expect it to be from the optical analogy (see figure 3 and appendix).

At this point, it is perhaps worth to briefly discuss the BEC-light analogy in slightly more detail. The time evolution of an interaction-free, un-trapped, 2-dimensional, BEC according to the Gross-Pitaevskii equation is formally equivalent to spatial propagation of a light beam in the paraxial approximation. This is, of course, the basis of our specific efforts to reproduce light-like behaviour in BECs. However, the analogous light beam is of sub-wavelength size, and the paraxial approximation describes the actual propagation of such beams very badly (it does, for example, ignore evanescent waves). It is therefore not surprising that BECs – even in the most light-like case of no interactions and no trap – often behave quite differently from light.

We model local absorption as a straightforward reduction in amplitude; in particular we neglect any interaction between the ’absorbed’ and left-over parts of the BEC. This is an idealisation of a situation which, we believe, can be approximated experimentally in different ways, for example by utilising a two-photon Raman process to couple out (move into an untrapped state) the part of the BEC which lies in the overlap region of two laser pulses Edwards et al. (1999). To achieve the necessary flexibility, our absorption pattern consists of up to two absorbing cross-hairs (the intensity cross-section is that of a narrow Gaussian, in our simulation often a single pixel wide; for a typical BEC size of 50$`\mu `$m, this corresponds to lines of light about 500nm wide), as well as an absorbing rectangular boundary with a Gaussian edge profile.

Figure 4 shows the BEC after the first few light pulses, starting with the trap ground state, through a light-pulse resonator of length $`L=0.2`$ and with a focal time $`f=0.5`$ (both in dimensionless time units). We use this as our ’standard’ light-pulse resonator. It will be seen that this behaves in many ways analogous to a stable optical resonator. Due to the losses, the number of particles changes during every period of the light-pulse resonator, which in turn changes the size of the self-interaction potential in the Gross-Pitaevskii equation, $`g|\psi |^2`$ (provided $`g0`$). As we keep the integral over the density normalised in our model, the reduction in the number of particles and any corresponding change in the interaction term size is represented as a decrease in $`g`$.

As long as the value of $`g`$ – and with it the potential – changes, no stationary eigenmode can form. This means that, for $`g0`$, no stationary eigenmode can form before the loss has become zero. In practice, the number of particles keeps diminishing exponentially, so zero loss can never be reached with any atoms still left. However, while atoms are still left, the loss can become very small. Then the BEC becomes very similar to the eigenmode corresponding to the eigenmode for the same value of $`g`$ in the hypothetical limit of no loss.

In order to calculate eigenmodes for any given value of $`g`$ in the no-loss limit, we re-normalise the integral over the density after each loss pulse without making a corresponding adjustment to $`g`$. This would correspond to either coherently replenishing the BEC after each loss pulse such that the number of atoms remains constant, or to tuning the value of $`g`$ to ’simulate’ this – neither of these are easily realisable experimentally. Nevertheless, the procedure gives stationary eigenmodes that correspond to the no-loss limit.

After a number of periods of the light-pulse resonator the eigenmode has formed, that is the BEC is not significantly changing any more over subsequent periods (apart from a uniform factor to the wave function). As a criterion for reaching this state we demand that the loss due to the aperture varied by less than 0.5%; this happened typically after about 40 iterations (light-pulse sequences), which takes several minutes to simulate on our desktop computer. Note that there appears to be an upper limit to the non-linear coefficient, $`g_{\mathrm{max}}`$, above which the BEC does not converge to a stable eigenmode. The exact value of $`g_{\mathrm{max}}`$ depends on the parameters of the light-pulse resonator. We determined this value for a number of different resonators and obtained values between $`80g_{\mathrm{max}}110`$.

Once the eigenmode has formed, the absorption due to each absorption event can be very low; we have achieved losses below 0.2% per absorption event. However, before the eigenmode has formed the losses can be very high; just how high depends on the starting conditions and the particular choice of shape of the loss pulse. Note that there is a trade-off between round-trip loss and number of round trips it takes to form eigenmode: thinner cross wires mean lower loss per round trip, but require more round trips. For well-chosen parameters, of the order of 10% of the BEC are left by the time the BEC begins to resemble the stationary eigenmode.

Figure 5 shows some of the stable patterns that emerge for a modest non-linearity ($`g=30`$, corresponding to approximately $`10^3`$ atoms of $`{}_{}{}^{87}Rb`$ in a $`20\pi `$ Hz trap) by varying the localised absorption pattern – a 100% absorptive cross-hair of 1 pixel width placed in crossing node lines (see figure 5). Like all other pictures in this paper (unless otherwise stated), this figure shows only the central $`6.25\times 6.25`$ units of the modelled area for clarity, and the grey values represent linear densities, ranging from 0 (black) to 0.2 (white). The patterns look very similar to Hermite-Gaussian modes, more so for small values of the non-linear parameter $`g`$, less so for large values (figure 6). In all cases, the eigenmodes have the tell-tale $`\pi `$ phase difference between adjacent peaks, just like the optical HG modes.

Repeating these simulations for a switched-off harmonic trap shows that the results are virtually indistinguishable from those obtained with the trap switched on. This is not surprising as the time scale of effects due to the trap (1 dimensionless unit) is several times larger than the time scale of effects due to the lens pulses (the focal time). It suggests that a series of lens pulses – a light-pulse resonator without absorption events – could act as a novel type of trap. Indeed, in the absence of absorption events, and to within the accuracy of the Gross-Pitaevskii equation, a series of light pulses acts as a loss-less trap. It is worth noting that, much like a stable laser resonator ’traps’ not only light waves but also light rays, a light-pulse resonator could perhaps not only trap atoms in a BEC but also hotter or Fermionic atoms.

If the series of light pulses, as well as any other potential (in particular the harmonic trap), is switched off after a stationary eigenmode has formed, the eigenmode evolves freely. Figure 7 investigates the size change of the eigenmode during this free evolution; the shape remains almost unchanged. This property is in analogy to structural stability of the eigenmodes of stable optical resonators, which can be understood in terms of imaging of every plane into every other plane Forrester et al. (2002).

All the results shown so far were calculated for our standard resonator with a time between pulses – corresponding to the resonator length – of $`L=0.2`$, and a lens-pulse focal time of $`f=0.5`$. Figure 8 shows $`n=1`$, $`m=0`$ eigenmodes from different light-pulse resonators. In the optical analogy, altering resonator parameters while keeping the resonator geometrically stable (that is, satisfying $`L<4f`$) results in eigenmodes of a different size; the analogous effect in BEC light-pulse resonators can be seen in figure 8.

## IV Conversion into Laguerre-Gaussian-like modes

To examine the similarities between the eigenmodes of light-pulse resonators and optical HG modes beyond the level of appearance, we investigate here the analogy of a conversion of optical HG modes, which have a rectangular symmetry, into circularly symmetric Laguerre-Gaussian (LG) modes under cylindrical focussing Beijersbergen et al. (1993). This conversion is due to a fairly subtle effect: the Gouy phase shift, which occurs when HG modes pass through a focus. It is interesting also because LG modes can contain a higher-charge vortex at their centre.

In the optical case, the cylindrical focussing that converts HG modes into LG modes is usually performed with a pair of cylindrical lenses. In analogy, we use here a pair of cylindrical-lens pulses, i.e. far off-resonant laser pulses with an intensity profile that varies quadratically in one direction and which is constant in the perpendicular direction. Figure 9 shows some results that were calculated for $`g=50`$. The density is certainly not shaped like a perfect ring; instead, most of the density is contained in a distorted ring. Also instead of containing a charge-$`l`$ vortex at the centre, the wave function contains $`l`$ vortices of charge 1. The conversion is therefore not perfect, but there are some indications that it is happening. In other simulations (not shown) we confirmed that this is also the case for different choices of $`g`$ (including $`g=0`$), and that, in the appropriate cases, the shape of the BEC also shows signs of the multiple concentric rings characteristic of LG modes with a radial mode index $`p>0`$.

In the optical case, the focal lengths of the cylindrical lenses and their positions need to be carefully matched to the parameters of the incoming HG mode to achieve good conversion into a LG mode. We tried to similarly optimise the parameters of the cylindrical-lens pulses. However, the similarity to a pure LG mode of the resulting density was always limited, which is not surprising as the BEC was initially not in a pure HG mode and as the evolution of the BEC is different from that of light. Finally, optimisation of the pulse parameters was not made easier by the complications in the focussing characteristics of a BEC mentioned earlier (figure 3).

## V Conclusions

The emergence of Hermite-Gaussian-like modes in a BEC is a very graphical further illustration of the similarity between BECs and laser light. However, any experimental verification of our scheme would have to take into account the high losses associated with the absorption events.

Alternatively, the absorption events could be replaced by far off-resonant pulses that locally disturb the BEC in places where the local density of the desired mode is zero, thereby effectively transferring a small part of the BEC in an undesired mode into a variety of other modes, amongst them the desired mode. No simulations of this scheme have been performed to date, so the magnitude of any loss saving is unknown.

Our results indicate that a series of lens pulses acts as a novel trap. Although analogy with optical resonators, in agreement with our approximate description with the Gross-Pitaevskii equation, would suggest that such a trap is loss-less, a more detailed microscopic description of the BEC predicts finite losses during the interaction with the lens pulses and when the density gets high due to mechanisms such as 3-body recombination Kagan et al. (1998); Fedichev et al. (1996).

As described in this paper, a light-pulse resonator confines a BEC in two dimensions. It should be possible to achieve confinement in all three dimensions by a combination of two orthogonal light-pulse resonators or similar arrangements. Alternatively, the rapid fall-off of the intensity away from the focal plane due to extremely tight focussing of the lens pulses, which leads to an approximately quadratic Stark potential along the propagation axis, could perhaps be used to extend the confinement to all three dimensions.

We are currently investigating the BEC analogy to holographic light shaping. In this way, a BEC can be shaped in two and three dimensions. This could, for example, be useful in quantum computation with arrays of trapped atoms Monroe (2002). The analogy can even be extended to the extremely versatile volume holograms, whereby the BEC analog of a controllable volume phase hologram – a far off-resonant light pulse with a controllable time-varying intensity – might even be easier to realise than the original.

###### Acknowledgements.

JC is a Royal Society University Research Fellow, PÖ acknowledges support from the Royal Society of Edinburgh. Financial support is also gratefully acknowledged from the UK Engineering and Physical Sciences Research Council (EPSRC).

## Appendix A Analytical focussing results

Let us briefly discuss the focussing dynamics in two dimensions. For low densities or small scattering lengths we can assume a non-interacting gas, i.e. $`g=0`$. Using the propagator for the now linear Schrödinger equation with a harmonic external potential we obtain the full dynamics of the condensate,

$`\mathrm{\Psi }(r,t)`$ $`=`$ $`\mathrm{exp}\left(i{\displaystyle \frac{r^2}{4}}\mathrm{cot}(\omega t)\right){\displaystyle \frac{1+i\mathrm{cot}(\omega t)}{1+i(\mathrm{cot}(\omega t)1/f)}}`$
$`\times \mathrm{exp}\left({\displaystyle \frac{r^2}{4\mathrm{sin}^2(\omega t)\left(1+i(\mathrm{cot}(\omega t)1/f)\right)}}\right),`$
where we have used the initial state

$$\mathrm{\Psi }(r,t=0)=\mathrm{exp}\left[\frac{1}{4}r^2i\frac{1}{4f}r^2\right],$$
(7)
This initial state is a ground state whose phase has been altered by a lens pulse of focussing time $`f`$. All lengths are in units of $`(\mathrm{}/2m\omega )^{1/2}`$ and the energy is in units of $`\mathrm{}\omega `$. From the minimum of the width of the Gaussian $`|\mathrm{\Psi }(r,t)|^2`$ we obtain the actual focussing time

$$t_f=\frac{1}{\omega }\frac{1}{2}\mathrm{arctan}(2f).$$
(8)
If $`f1`$ we get $`t_f=\pi /4`$. In the opposite limit, $`f1`$, $`t_ff`$, in accordance with figure 3.

We can also calculate an analytical expression for the focussing time when the interactions between the atoms are not negligible and the inequality $`\mu /\mathrm{}\omega 1`$ (where $`\mu `$ is the chemical potential) is satisfied – the Thomas-Fermi regime. During the focussing the condensate is structurally stable, i.e. the shape of the cloud is preserved and only the time and length scales change during the evolution. We rewrite the Gross-Pitaevskii equation in the hydrodynamic form

$`{\displaystyle \frac{\rho }{t}}+(\rho 𝐯)=0`$ (9)
$`m{\displaystyle \frac{𝐯}{t}}=\left({\displaystyle \frac{1}{2}}mv^2+{\displaystyle \frac{1}{2}}m\omega ^2r^2+g\rho {\displaystyle \frac{\mathrm{}^2}{2m}}{\displaystyle \frac{^2\sqrt{\rho }}{\sqrt{\rho }}}\right),`$
(10)
where $`\rho (r,t)`$ is the density with the velocity $`𝐯`$ defined as $`𝐯=(\mathrm{}/m)\mathrm{\Theta }(𝐫,t)`$ and $`\mathrm{\Theta }(𝐫,t)`$ is the gradient of the condensate phase. In the Thomas-Fermi approximation we neglect the last term on the right-hand side of Eq. (10). The density will now take the form

$$\rho (r,t)=\frac{1}{gb(t)^2}[\mu \frac{1}{2}m\omega ^2(\frac{r}{b(t)})^2],$$
(11)
where $`\mu `$ is the chemical potential at $`t=0`$. If we choose the phase to be quadratic in $`r`$,

$$\mathrm{\Theta }(r,t)=\frac{m}{2\mathrm{}}r^2q(t),$$
(12)
and insert this into Eqs. (9) and (10) together with the parabolic density $`\rho (r,t)`$, we see that the dynamics is completely described by the parameter $`b(t)`$ if and only if $`b(t)`$ fulfills

$$\ddot{b}=\omega ^2(\frac{1}{b^3}b)$$
(13)
with $`q(t)=\dot{b}/b`$ and the initial conditions $`b(0)=1`$ and $`\dot{b}(0)=1/f`$. Equation (13) can be solved exactly to give

$$b(t)=\sqrt{1+\frac{1}{2f^2}\frac{1}{2}\sqrt{\frac{1}{f^4}+\frac{4}{f^2}}\mathrm{sin}\left(2t+\mathrm{arctan}(\frac{1}{2f})\right)}$$
(14)
The focussing time, defined by $`\dot{b}=0`$, is consequently

$$t_f=\frac{1}{\omega }\frac{1}{2}\mathrm{arctan}(2f)$$
(15)
As can be seen from Eqs. (8) and (15) the focussing time is the same both for the noninteracting case and in the Thomas-Fermi limit. This is a coincidence and holds only in the self-similar situation and in 2D since the radial excitation frequencies are given by $`\mathrm{\Omega }=2n\omega `$ for the ideal gas and $`\mathrm{\Omega }=\omega \sqrt{2n^2+2nm+2n+m}`$ Stringari (1998) for the Tomas-Fermi cloud. For $`n=1`$ corresponding to the lowest breathing mode, i.e. focusing, the frequencies are the same.