path: root/Giuliani_Jauslin_Lieb_2015.tex

\documentclass{kiss}
% load packages
\usepackage{header}
% bibliography commands
\usepackage{BBlog}
% miscellaneous commands
\usepackage{toolbox}
% main style file
\usepackage{iansecs}

\definecolor{darkgreen}{HTML}{32CD32}

\def\defd#1{{\bf #1}}

\begin{document}

\pagestyle{empty}
{\LARGE\bf\hfil A Pfaffian formula\par
\bigskip
\hfil for monomer-dimer partition functions}\par
\hugeskip

{\bf\hfil Alessandro Giuliani, Ian Jauslin, Elliott H.~Lieb}\par
\hugeskip
\hfil 2015
\hugeskip

\indent We consider the monomer-dimer partition function on arbitrary finite planar graphs and arbitrary monomer and dimer weights, with the restriction that the only non-zero monomer weights are those on the boundary. We prove a Pfaffian formula for the corresponding partition function.  As a consequence of this result, multipoint boundary monomer correlation functions at close packing are shown to satisfy fermionic statistics.  Our proof is based on the celebrated Kasteleyn theorem, combined with a theorem on Pfaffians proved by one of the authors, and a careful labeling and directing procedure of the vertices and edges of the graph.

\hugeskip

\tableofcontents

\vfill
\eject

\pagestyle{plain}
\setcounter{page}1

\section{Introduction}

\indent The monomer-dimer problem is one of the important classical structures in statistical mechanics and computer science. It starts with a {\it graph} $g$, which is a collection of points, called {\it vertices}, and lines, called {\it edges}, between specified pairs of points. A dimer is an object that occupies a single edge and its endpoints, and a monomer is an object that occupies a single vertex. A {monomer-dimer covering} of $g$ (hereafter refered to as an MD covering) is a collection of monomers and dimers (that is to say vertices and edges) such that every vertex is covered by exactly one of these objects, that is by either a monomer or a dimer. Note that, in any MD covering, the number of vertices in $g$ is equal to the number of monomers plus twice the number of dimers. The present work is devoted to {\it planar} graphs (which are those that can be drawn in $\mathbb R^2$ without edge crossings).

\indent The classical problem associated with MD overings is their enumeration at fixed number of monomers. The object of this work is to find formulas for the generating function of this enumeration problem:
\begin{equation}
\Xi(z):=\sum_{\mathrm{MD\ coverings}}z^{\mathrm{number\ of\ monomers}}.
\label{eqXizdef}\end{equation}
Clearly, $\Xi(z)$ is a polynomial in $z$, and $z$ is called the {\it monomer fugacity}. This polynomial has all its zeros on the imaginary axis~[\cite{HL70}, \cite{HL72}]. In addition, the summation in~(\ref{eqXizdef}) can be generalized by assigning weights to edges and/or vertices.

\indent In the pure dimer case, where $z=0$, $\Xi$ has been shown by Temperley and Fisher (for the square lattice) [\cite{TF61}]  and by Kasteleyn (for general planar graphs) [\cite{Ka63}] to be expressible as a Pfaffian (which is convenient since Pfaffians can be computed as square roots of determinants). However, when monomers are allowed to appear, such a Pfaffian formula is thought to be impossible (at least a Pfaffian formula for the {\it full} MD problem on {\it any} planar graphs): indeed it has been shown [\cite{Je87}] that the enumeration of MD coverings of generic planar graphs is ``computationally intractable'', whereas Pfaffians can be computed in polynomial time. More precisely, [\cite{Je87}] proves that the enumeration of MD coverings of generic planar graphs is
``$\# P$ complete'', which implies that it is believed not to be computable in polynomial time.

\indent However, by introducing restrictions on the location of monomers, such a result can be proven in some cases. Namely, in [\cite{TW03}, \cite{Wu06}], the authors use a Pfaffian formula to compute the partition function of a system with a {\it single} monomer located on the boundary of a finite square lattice. In [\cite{PR08}], the MD problem is studied on the square lattice on the half-plane with the restriction that the monomers are {\it fixed} on points of the boundary. They derive a Pfaffian formula for this case, and use it to compute the scaling limit of the multipoint boundary monomer correlations. Finally, in [\cite{AF14}], it is shown that if the monomers are {\it fixed} at any position in a square lattice, then the partition function can also be written as a Pfaffian. In addition, the authors use their formula for 
computing the asymptotics of monomer correlations, thus generalizing the classical results by Fisher, Hartwig and Stephenson [\cite{FS63}, \cite{Ha66}, \cite{FH69}]
for monomer correlations along a row, column  or main diagonal.

\indent In the present work, we prove that, on an {\it arbitrary} planar graph, the {\it boundary} MD partition function (in which the monomers are restricted to the boundary of the graph, but are not necessarily fixed at prescribed locations) with arbitrary dimer and monomer weights can be written as a Pfaffian. 
By differentiation with respect to the monomer weights, we also obtain a fermionic Wick rule for boundary monomer correlations. 
There are two main novelties in our result. First, we obtain the Pfaffian formula for the partition function with arbitrary weights rather than for 
the problem with monomers at fixed locations. Second, we study the boundary MD problem on {\it any} planar graph,
in particular for graphs that may not admit a transfer matrix treatment. 
\bigskip

{\bf Remarks}:
\listparpenalty
\begin{itemize}
\item An alternative approach for the boundary MD problem on an $N\times M$ rectangle (by which we mean $N$ vertices times $M$ vertices) with monomers allowed only on the upper and lower sides 
would be to use the transfer matrix technique [\cite{Li67}]. In that case, the boundary MD partition function is written as $x_M\cdot V^{M-1}x_1$ where $V$ is the
($N\times N$) transfer matrix and $x_1$ and $x_M$ are vectors determined by the boundary condition at the boundaries $y=1$ and $y=M$ respectively. 
Since the monomers are only allowed on these two boundaries, the matrix $V$ is the transfer matrix for {\it pure} dimer coverings, which can be 
diagonalized as in [\cite{Li67}]. The partition function can then be computed by setting the vectors $x_1$ and $x_M$ appropriately. 
\item The boundary monomer correlations at close-packing are critical, in that if the graph is ``regular enough'' (e.g., 
if it is a finite portion of a lattice) they decay polynomially at large distances, 
like $1/(distance)$, asymptotically as the size of the graph tends to infinity. 
See [\cite{PR08}] for a proof of this fact on the square lattice on the half-plane. 
If the graph is a discrete, regular, approximation of a finite domain of $\mathbb R^2$, 
the scaling limit of these correlations 
is expected to exist and to be conformally invariant under conformal mappings of the domain, in analogy with other observables 
of the critical 2D Ising model and of the close-packed dimer model [\cite{Ke00}, \cite{Ke01}, \cite{Sm01}, \cite{Sm10}, \cite{CHI15}, \cite{Du11}, \cite{Du15}].
In particular, they are expected to coincide with those of complex chiral free fermions [\cite{PR08}].
It is unclear whether this scaling limit is stable under perturbations violating planarity (e.g., under the addition of small dimer weights along extra 
edges crossings). Our Pfaffian formula offers a starting point for a perturbative multiscale analysis of the problem, in the spirit of [\cite{PS}, \cite{Sp00}, \cite{GGM12}, \cite{GMT15b}, \cite{GMT15}].
\item An alternative approach for the boundary MD problem on generic
planar graphs is via the random current representation developed by
Aizenman [\cite{Ai82}]. It has been recently observed
[\cite{AD}] that this representation, adapted to planar lattices, implies, for
purely geometrical
reasons, the validity of the fermionic Wick rule both for boundary spin
correlations in the nearest neighbor Ising model, and might imply the
same for boundary monomer correlations in the dimer model.
Their method also suggests a stochastic geometric perspective on the
emergence of planarity at the critical points of non-planar 2D models, in the sense of the previous item.
\item It may be worth noting that the MD partition function can be computed exactly in some cases, e.g. on the complete graph [\cite{ACM14}].
\end{itemize}
\unlistparpenalty

\indent We will now state our main result more precisely, for which we need some notation. Let $\mathcal G$ denote the set of finite planar graphs with edge-weights and vertex-weights, embedded in $\mathbb R^2$, that have an even number of vertices, and contain no {\it double edges} or {\it self-contractions} (that is the endpoints of an edge are distinct, and no two edges share the same endpoints). Note that these graphs are not necessarily connected. The 
evenness condition is not restrictive, in that a graph with an odd number of vertices can always be reduced to an even one, by adding an isolated (disconnected) vertex.

\indent Given $g\in\mathcal G$, its \defd{boundary graph} $\partial g$ is defined as the sub-graph of $g$ containing the edges and vertices that can be connected to infinity without crossing any edge of $g$ (here we say that an edge can be connected to infinity without crossing any other edge, if a point at the center of the edge can be). The set of vertices of $g$ is denoted by $\mathcal V(g)$ and its set of edges by $\mathcal E(g)$. The edge linking two vertices $v_1$ and $v_2$ will be denoted by $\{v_1,v_2\}\equiv\{v_2,v_1\}$. The weight of a vertex $v\in\mathcal V(g)$ (i.e. the fugacity of a monomer located at $v$) is denoted by $\ell_v$ and the weight of an edge $\{v_1,v_2\}\in\mathcal E(g)$ (i.e. the fugacity of a dimer located at $\{v_1,v_2\}$) is denoted by $d_{\{v_1,v_2\}}\equiv d_{v_1,v_2}$. The number of vertices in $g$ in denoted by $|g|$. 
In the following we will often consider {\it directed} graphs, which are obtained by assigning a direction to every edge: if the edge $\{v_1,v_2\}$ is directed from $v_1$ to $v_2$, we write $v_1\succ v_2$.

\indent The set of MD coverings of $g$ is denoted by $\Omega(g)$ and the set of pure dimer coverings by $\Omega_0(g)$. Given an MD covering $\sigma\in\Omega(g)$, we denote the set of vertices covered by monomers by $\mathfrak M(\sigma)\subset\mathcal V(g)$ and the set of edges covered by dimers by $\mathfrak D(\sigma)\subset\mathcal E(g)$. The \defd{boundary MD partition function} of a graph $g$ is defined as the partition function of MD coverings of $g$ in which the monomers are restricted to vertices of $\partial g$:
\begin{equation}
\Xi_\partial(\bm\ell,\mathbf d):=\sum_{\displaystyle\mathop{\scriptstyle\sigma\in\Omega(g)}_{\mathfrak M(\sigma)\subset\mathcal V(\partial g)}}\prod_{v\in\mathfrak M(\sigma)}\ell_v\prod_{e\in\mathfrak D(\sigma)}d_e.
\label{eqpartfnboundary}\end{equation}
Note that restricting the monomers of $\sigma$ to be on boundary vertices can be enforced by setting all other $\ell_v$'s to 0.

\indent The Pfaffian of a $2n\times2n$-dimensional antisymmetric matrix $(A_{i,j})$
is defined as
\begin{equation}
 \mathrm{pf}(A):=\frac1{2^nn!}\sum_{\pi\in\mathcal
S_{2n}}(-1)^\pi\prod_{i=1}^nA_{\pi(2i-1),\pi(2i)}
\label{eqpfaffdef}\end{equation}
where $\mathcal S_{2n}$ denotes the set of permutations of $\{1,\cdots,2n\}$ and $(-1)^\pi$ is the signature of $\pi\in\mathcal S_{2n}$.
\bigskip

\theoname{Theorem}{Main result}\label{theomain}
For every $g\in\mathcal G$, the edges of $g$ can be directed and its vertices labeled $(v_1,\cdots,v_{|g|})$ in such a way that, by defining
\begin{equation}
a_{i,j}(\mathbf d):=\left\{
\begin{array}{l@{\ }l}
 +d_{v_i,v_j}&\mathrm{if\ }\{v_i,v_j\}\in\mathcal E(g)\ \mathrm{and\ }v_i\succ v_j\\
 -d_{v_i,v_j}&\mathrm{if\ }\{v_i,v_j\}\in\mathcal E(g)\ \mathrm{and\ }v_i\prec v_j\\
 0&\mathrm{otherwise}
\end{array}
\right.
\label{eqAdef}\end{equation}
and, for $i<j$,
\begin{equation}
A_{i,j}(\bm\ell,\mathbf d):=a_{i,j}(\mathbf d)-(-1)^{i+j}\ell_i\ell_j
\label{eqpolysta}\end{equation}
and $A_{j,i}(\bm\ell,\mathbf d):=-A_{i,j}(\bm\ell,\mathbf d)$, the boundary MD partition function on $g$ is given by
\begin{equation}
\Xi_\partial(\bm\ell,\mathbf d)=\mathrm{pf}(A(\bm\ell,\mathbf d)).
\label{eqtheo}\end{equation}
\endtheo
\bigskip

{\bf Remarks}:
\listparpenalty
\begin{itemize}
\item By setting some weights $\ell_v$ to 0, the location of the monomers can be further restricted. In particular, the partition function (and correlation functions) with {\it fixed} monomers can be expressed using the Pfaffian formula~(\ref{eqtheo}), as has been done for the special cases studied in [\cite{TW03}, \cite{PR08}].
\item Similarly, by setting edge weights to 0, dimers can be excluded from any part of the graph.
\item It may be worth noting that the weights $d_e$ and $\ell_v$ may be complex.
\item Our result provides a polynomial-time algorithm for computing boundary MD partition functions on generic planar graphs. 
See appendix \ref{app.A} for examples. 
\item Based on theorem \ref{theomain}, we have derived an algorithm (see appendix~\ref{appalg}) that allows us to compute the {\it full} MD partition function (as opposed to the boundary MD partition function) on an arbitrary planar graph, which is more efficient than the naive enumeration algorithm. 
For instance, if $g$ is an $L\times M$ rectangle on the square lattice, our algorithm requires 
$O((LM)^3 2^{(LM)/2})$ operations, while the naive algorithm requires $O((LM)^32^{LM})$. In the rectangular case, a 
transfer matrix approach would be even faster, completing the computation in $O((LM)^32^L)$ operations~[\cite{Ko06c}], but our algorithm 
does not require the graph to be treatable via a transfer matrix approach. 
\item As a side remark, note that Monte Carlo methods methods can be even faster, i.e., polynomial in the size of the system~[\cite{KRS96}], but they provide correct results only with high probability rather than with certainty.
\end{itemize}
\unlistparpenalty
\bigskip

\indent If we derive $\Xi_\partial(\bm\ell,\mathbf d)$ with respect to $\bm \ell$ and then set $\bm\ell$ to zero, we obtain the multipoint 
monomer correlations at close packing:
\begin{equation}
M_n(i_1,\cdots,i_{2n}):=\left.\frac1{\Xi_\partial(\mathbf0,\mathbf d)}\frac{\partial^{2n}\Xi_\partial(\bm\ell,\mathbf d)}{\partial\ell_{i_1}\cdots\partial\ell_{i_{2n}}}\right|_{\ell_1=\cdots=\ell_{|g|}=0}.
\label{eqcorrdef}\end{equation}
An important corollary of theorem \ref{theomain} is that $M_n(i_1,\cdots,i_{2n})$ satisfies the fermionic Wick rule.
\bigskip

\theoname{Corollary}{Fermionic Wick rule}\label{corrmain}
In the same setting as theorem \ref{theomain},
\begin{equation}
M_n(i_1,\cdots,i_{2n})=\mathrm{pf}(\mathfrak M_{i_1,\ldots,i_{2n}}),
\label{eqwick}\end{equation}
where $\mathfrak M_{i_1,\ldots,i_{2n}}$ is the $2n\times 2n$ antisymmetric matrix whose $(j,j')$-th entry with $j<j'$ is $M_1(i_j,i_{j'})$.
\endtheo
\bigskip

\indent As stated in theorem~\ref{theomain}, the edges and vertices of $g$ must be directed and labeled in a special way. In particular, the direction of the edges must satisfied a so called {\it Kasteleyn} condition, and the labeling must satisfy a {\it positivity} condition. The positivity condition ensures that the terms that appear in the Pfaffian add up constructively and reproduce the MD partition function. The Kasteleyn condition is used to prove the positivity of a graph: if such a condition holds, then it suffices to look at a single dimer covering of $g$ to prove its positivity.

\indent The main ingredient of the proof of our result is to show that, having directed and labeled the graph in an appropriate way, every sub-graph constructed from $g$ by removing the vertices which support monomers satisfies both the Kasteleyn and positivity conditions. Proving that the sub-graph satisfies the Kasteleyn condition is easy (provided the monomers live on the boundary of the graph), but proving its positivity is more of a challenge. The basic idea is to construct a dimer covering (a dimer covering is an MD covering that has no monomers) of the sub-graph that is obviously positive. However, in some cases, it may be difficult to find such a dimer covering. In order to facilitate this task, we introduce the notion of {\it extended dimer coverings} of $g$ which are a generalization of dimer coverings, and are easier to construct. An extended dimer covering is a dimer configuration in which every vertex is covered by an {\it odd} number of dimers (thus generalizing dimer coverings, which cover every vertex {\it once}). We will show below how to construct an extended dimer covering of any sub-graph of $g$ from which we can prove the positivity of the sub-graph.
\bigskip

\indent For the purpose of exposition, we will first discuss the case of {\it
simple} planar graphs, consisting of a single circuit of vertices
(i.e. a sequence of $n$ vertices $(v_1,\cdots,v_n)$ such that $v_i$ is
connected to $v_{i+1}$ and $v_n$ to $v_1$) that may or may not contain
internal edges (so that all vertices are on the boundary). We will then move
on to graphs consisting of a boundary circuit with an even number of vertices, encircling a connected interior.
We then show that the general case can be reduced to the previous one, by
suitably adding auxiliary vertices and edges.
\bigskip

\indent The structure of the paper is the following.
\begin{itemize}
\item In section~\ref{secpreliminaries}, we define and discuss some of the ingredients of the proof of the Pfaffian formula. Namely, we define the Kasteleyn and positivity conditions and state a theorem on Pfaffians, based on a result of~[\cite{Li68}], which is at the basis of the Pfaffian formula for the boundary MD partition function. Moreover, we prove corollary \ref{corrmain}. 
\item In section~\ref{secsimple}, we prove theorem \ref{theomain} in the case of simple graphs.
\item In section~\ref{secprelin}, we present some more preliminary results that will be used to generalize the discussion to more general graphs. Namely, we discuss some properties of Kasteleyn graphs, show how a graph can be directed in order to satisfy the Kasteleyn condition, and define extended dimer coverings.
\item In section~\ref{seceven}, we generalize the discussion of simple graphs and prove theorem \ref{theomain} in the more general class of graphs whose interior is connected 
and has an even number of vertices.
\item In section~\ref{secenclosed}, we turn to a more general class of graphs in which the connectedness condition is dropped, and prove theorem \ref{theomain} also in this case.
\item In section~\ref{sec7}, we show how to add edges and vertices to a graph in a way that does not change the partition function
and reduces it to the previous case.
\end{itemize}
\bigskip

\indent In this paper, we have adopted a rather pedagogical approach. For readers that want to get to the result without going through all of the proofs can follow the following
\bigskip

\delimtitle{\bf Short track}
\listparpenalty
\begin{itemize}
\item read section~\ref{subseckasteleyn} for the main definitions,
\item skip to proposition~\ref{propdirectkasteleyn} for an algorithm to direct graphs,
\item move on to section~\ref{subsecextendeddimer} for the definition of extended dimer coverings
\item optionally read proposition~\ref{propcovextended} for an algorithm to construct an extended dimer covering of any even connected graph,
\item skip proposition~\ref{propextendedkasteleyn} and jump to section~\ref{secenclosed},
\item read the beginning of section~\ref{secenclosed} until (including) the paragraph labeled ``\ref{recipeenclosed}'',
\item read section~\ref{sec7} for an algorithm to reduce generic planar graphs to enclosed graphs.
\end{itemize}
\enddelim
\unlistparpenalty



\section{Preliminaries}\label{secpreliminaries}
In this section, we present the key results that will allow us to prove the
Pfaffian formula for the boundary MD partition function. We will restrict the discussion to the ingredients needed to treat simple graphs, and will proceed to the properties needed for more general graphs in section~\ref{secprelin}.
\bigskip

\subsection{Kasteleyn's theorem}\label{subseckasteleyn}
In this section, we discuss a method introduced by P.~Kasteleyn [\cite{Ka63}]
to write the partition function of dimers on planar graphs as a Pfaffian.
In order to construct the matrix $A$ whose Pfaffian yields the partition
function of dimers, the graph $g$ must first be oriented and its vertices
labeled in a way that satisfies two conditions: the {\it Kasteleyn} and
{\it positivity} conditions described below. 

\point{\bf The Kasteleyn condition. }
Before discussing the Kasteleyn condition, we first define a
\defd{counterclockwise circuit} $c=(v_1,\cdots,v_{|c|})$ with $|c|\ge 3$ as an ordered sequence of
vertices $v_i\in\mathcal V(g)$ that are such that
\begin{itemize}
\item $v_i\neq v_j$ for all $i\neq j$,
\item for all $1\le i\le |c|$, $\{v_i,v_{i+1}\}\in\mathcal E(g)$, where
$v_{|c|+1}\equiv v_1$,
\item the path $v_1\rightarrow\cdots\rightarrow v_{|c|}\rightarrow v_1$ 
winds in the counterclockwise direction.
\end{itemize}
Note that the notion of counterclockwise circuit does not require the graph to be 
directed. 
The ``counterclockwise'' adjective will be omitted in the following. Moreover, 
we will (obviously) identify circuits obtained from each other by a cyclic permutation.


\indent The \defd{boundary} of a graph $g$ is the set of vertices and edges that
are accessible from infinity. A graph is said to have a
\defd{boundary circuit} if its boundary forms a circuit. Note that all finite
graphs have a boundary, but not always a boundary circuit (e.g. two
vertices connected by an edge). In this paper we will first be concerned
with graphs that have a boundary circuit, and in section~\ref{secboundarycircuit} we will
show how to reduce general graphs to graphs with a boundary circuit. 

\indent Given an edge $\{v_i,v_{i+1}\}$ for $1\le i\le |c|$,
the edge is said to be \defd{forwards} if $v_i\succ v_{i+1}$ and
\defd{backwards} if $v_i\prec v_{i+1}$; and similarly for 
$\{v_{|c|},v_1\}$. A circuit $c$ is said to be \defd{oddly-directed} if it contains an {\it odd} number of {\it backwards} edges and \defd{evenly-directed} if it contains an {\it even} number of {\it backwards} edges. In addition a circuit will said to be \defd{good} if it is {\it oddly-directed} and encloses an {\it even} number of vertices, or it is {\it evenly-directed} and encloses an {\it odd} number of vertices.

\indent Furthermore, given $\nu\ge 1$ and two circuits $c_1$ and $c_2$ that have a
string of vertices in common appearing in the reverse order, that is
\begin{equation}
c_1=(v_1,\cdots,v_{\nu+1},v_{\nu+2},\cdots,v_{|c_1|}),\quad
c_2=(v_{\nu+1},\cdots,v_{1},v_{\nu+2}',\cdots,v_{|c_2|}')
\label{eqmergecircuit}\end{equation}
with $v_i\neq v_j$ for all $i\neq j$ and $v_i\neq v'_j$ for all $i,j$.
The edges $\{v_i,v_{i+1}\}$ with $i\le\nu$ are
the edges that $c_1$ and $c_2$ share. We define the \defd{merger} of $c_1$
and $c_2$ as the circuit
\begin{equation}
c_1\Delta
c_2:=(v_{\nu+1},\cdots,v_{|c_1|},v_1,v_{\nu+2}',\cdots,v_{|c_2|}').
\label{eqsymdiff}\end{equation}
See figure~\ref{figmerger} for an example. A circuit $c$ is said to be \defd{minimal} if it is not a merger, that is if for any pair of circuits $c_1$ and $c_2$ as in~(\ref{eqmergecircuit}), $c\neq c_1\Delta c_2$. A circuit $c_1$ is said to be \defd{maximal} if it cannot be merged with any other circuit, that is if there is no $c_2$ as in~(\ref{eqmergecircuit}). Note that a minimal circuit may have vertices and edges (and even circuits) in its interior, see figure~\ref{figminimalcircuit} for an example.  Vice versa, a circuit without vertices in its interior is minimal. Minimal circuits with no interior vertices are called {\it mesh cycles} in [\cite{Ka63}].
\bigskip

\begin{figure}
\hfil\includegraphics{Figs/circuit.pdf}\par\penalty10000
\caption{A merger. The circuit $c_1$ consists of the vertices rendered as {\color{red}red} (color online) upward-pointing triangles and {\color{darkgreen}green} circles, and the edges connecting them. The circuit $c_2$ consists of the vertices rendered as {\color{blue}blue} downward-pointing triangles and {\color{darkgreen}green} circles, and the edges connecting them. The merger $c_1\Delta c_2$ consists of the vertices rendered as {\color{red}red} upward-pointing triangles and {\color{blue}blue} downward-pointing triangles, and the edges connecting them. The vertices that are rendered as superimposed upward- and downward-pointing triangles, half red and half blue, should be interpreted as {\it both} red upward-pointing triangles {\it and} blue downward-pointing triangles.}
\label{figmerger}
\end{figure}
\bigskip

\begin{figure}
\hfil\includegraphics{Figs/minimal_circuit.pdf}\par\penalty10000
\medskip
\caption{In this example, there are two minimal circuits. The first minimal circuit consists of the vertices rendered as {\color{red}red} (color online) left-pointing triangles, and the edges connecting them. The second minimal circuit consists of the vertices rendered as {\color{blue}blue} right-pointing triangles, and the edges connecting them. The vertex that is rendered as superimposed left- and right-pointing triangles, half red and half blue, should be interpreted as {\it both} a red left-pointing triangle {\it and} a blue right-pointing triangle.}
\label{figminimalcircuit}\end{figure}
\bigskip

\theo{Definition}\label{defkasteleyn}
A directed graph $g\in\mathcal G$ is said to be \defd{Kasteleyn} if every
minimal circuit of $g$ is good, or if there are no minimal circuits in $g$.
\endtheo
\bigskip

\indent The adjective ``minimal'' can be dropped from definition~\ref{defkasteleyn}, as shown in the following lemma, which we will prove in section~\ref{subsecpropkasteleyn}.
\bigskip

\theo{Lemma}\label{lemmakasteleyncomplete}
Every circuit of a Kasteleyn graph is good.
\endtheo
\bigskip

{\bf Remark}: Note that, although our definition is slightly different from that used originally by Kasteleyn in [\cite{Ka63}], it can easily be 
recognized to be equivalent. In fact, the assumption of [\cite{Ka63}, item (A) on p.290], in light of [\cite{Ka63}, item (D) on p.290], 
is equivalent, in our language, to the fact that all even circuits are good (here, ``even'' refers to the number of vertices in the circuit, and is unrelated to the notion of ``evenly-directed'' defined above). Moreover, [\cite{Ka63}, item (C) on p.290] guarantees that 
both even and odd circuits are good. 
\medskip

\indent An important result of [\cite{Ka63}] is that every finite planar graph can be directed in such a way that it is Kasteleyn. 
A simple directing procedure alternative to that proposed in [\cite{Ka63}] can be found in [\cite{LL93}]. 
We will actually need a slightly generalized version of this directing procedure, 
which applies to graphs that are partially directed.
\bigskip

\theo{Proposition}\label{propdirectkasteleyn}
Let $g\in\mathcal G$ be a graph some of whose edges may be directed. If
every circuit that is thus directed is good, then the undirected
edges of $g$ can be directed in such a way that the resulting graph is
Kasteleyn.
\endtheo
For a proof and an algorithmic construction, see section \ref{subsecpropkasteleyn}.
\bigskip

\point{\bf The positivity condition.}
We now discuss the {\it positivity} condition.
The condition depends crucially on how the vertices of the graph are labeled.
It may appear to be merely a question of nomenclature, but it is more than
that: the labeling determines the order of the rows in the Pfaffian and
thereby affects its overall sign. We define the notion in precise terms:
a \defd{labeling} $\omega$ of the vertices of $g$ is a bijection
from $\mathcal V(g)$ to $\{1,\cdots,|g|\}$.

\indent Given a vertex labeling $\omega$, a
pure dimer covering $\sigma\in \Omega_0(g)$, which we write as
$$\sigma=\{(v_1,v_2),\cdots,(v_{|g|-1},v_{|g|})\}$$
with $v_{2i-1}\succ v_{2i}$, is said to be \defd{positive} if the
permutation
$\pi^{(\omega)}_\sigma\in\mathcal S_{|g|}$ defined by
$\pi^{(\omega)}_\sigma(i)=\omega(v_i)$ has a positive signature. Note that
the sign of $\sigma$ remains unchanged if $(v_{2i-1},v_{2i})$
and $(v_{2j-1},v_{2j})$ are exchanged.
\bigskip

\theo{Definition}\label{defpositivity}
Given a vertex labeling $\omega$, a directed graph $g$ is said to be
\defd{positive} if all of its dimer coverings are positive, or if it has no dimer coverings.
\endtheo

\indent The following proposition is the basis of Kasteleyn's theorem [\cite{Ka63}].
\bigskip

\theoname{Proposition}{Uniform positivity}\label{propkasteleyn}
 Given a vertex labeling $\omega$, a Kasteleyn graph $g$ that admits a dimer covering is positive if and
only if one of its dimer coverings is positive.
\endtheo

\indent Note that, in light of this proposition, every non-positive labeling can be made positive by 
switching two labels. 

\bigskip

\indent We are finally in the position of stating Kasteleyn's theorem. Given a positive Kasteleyn graph $g\in\mathcal G$, let, for $i,j=1,\cdots,|g|$ with $i<j$,
\begin{equation}
 a_{i,j}(\mathbf d):=\left\{
 \begin{array}{l@{\ }l}
  +d_{v_i,v_j}&\mathrm{if\ }\{v_i,v_j\}\in\mathcal E(g)\ \mathrm{and\ }v_i\succ v_j\\
  -d_{v_i,v_j}&\mathrm{if\ }\{v_i,v_j\}\in\mathcal E(g)\ \mathrm{and\ }v_i\prec v_j\\
  0&\mathrm{otherwise}
 \end{array}
 \right.
\label{eqadef}\end{equation}
in which $v_i$ is a shorthand for
$\omega^{-1}(i)$. Proposition~\ref{propkasteleyn} implies that the terms
in
the Pfaffian $\mathrm{pf}(a(\mathbf d))$ (see~(\ref{eqpfaffdef})) add up
constructively, which in turn implies the following
\bigskip

\theoname{Theorem}{Kasteleyn's theorem}\label{theokasteleyn}
Given a positive Kasteleyn graph $g\in\mathcal G$, the partition function $\Xi(0,\mathbf d)$ of pure dimer coverings of $g$ is given by
 \begin{equation}
  \Xi(0,\mathbf d)=\mathrm{pf}(a(\mathbf d)).
 \label{eqkasteleyntheo}\end{equation}
\endtheo
\medskip

\indent Note that, as commented above, every planar graph can be directed and labeled so as to make it Kasteleyn and positive. 
We remark that there are several directing procedures and labelings that ensure the Kasteleyn and positivity conditions. 
In the following, we are interested in proving that the sub-graphs obtained by erasing some vertices on the boundary 
(those at the monomer locations) are also Kasteleyn and positive. The subtle property to prove is the positivity of all such sub-graphs,
which is false in general. 
The goal of this paper is to find one good labeling of the full graph, guaranteeing positivity of all these sub-graphs. 

\subsection{A theorem on Pfaffians}\label{subsecpfaffian}

\indent The basic strategy to prove our main result is to combine Kasteleyn's theorem with a general theorem
about Pfaffians [\cite{Li68}], proved by one of us, which appears
at first glance to compute the
full MD partition function but fails to do so because of sign problems. Our
goal will be to show that these sign problems can be dealt with, if one
restricts the monomer locations to be on the boundary of a planar
graph, by making a careful choice of the direction and labeling of $g$.
\bigskip

\point{\bf Statement of the theorem on Pfaffians.}
We first state the theorem on Pfaffians, which is a slight generalization
of that proved in [\cite{Li68}].
\bigskip

\theoname{Theorem}{\rm[\cite{Li68}]}\label{theolieb}
Given an even positive integer $N$, an antisymmetric $N\times N$ matrix $a$,
and a collection of weights $\bm\ell=(\ell_i)_{i=1,\cdots,N}$, let
\begin{equation}
A_{i,j}(\bm \ell):=a_{i,j}-(-1)^{i+j}\ell_i\ell_j
\label{eqpolystal}\end{equation}
for $i<j$ and $A_{i,j}(\bm \ell)=-A_{j,i}(\bm \ell)$ for $i>j$, we have
\begin{equation}
\mathrm{pf}(A(\bm \ell))=\sum_{k=0}^{N/2}\sum_{\displaystyle\mathop{
\scriptstyle\mathcal
I\subset\{1,\cdots,N\}}_{|\mathcal
I|=2k}}\mathrm{pf}(\left[a\right]_{\mathcal I})\prod_{i\in\mathcal
I}\ell_i
\label{eqliebtheo}\end{equation}
in which
$\left[a\right]_{\mathcal I}$ denotes the matrix obtained from $a$ by
removing the $i$-th line and column for every $i$ in $\mathcal I$, and if $\mathcal I=\{1,\cdots,N\}$, then $\mathrm{pf}([a]_{\{1,\cdots,N\}})\equiv1$.
\endtheo
\medskip

\indent In [\cite{Li68}], the theorem was proved in the case in which the $\ell_i$
are equal, but the proof is immediately generalizable to arbitrary
$\bm \ell$. The only change needed in the proof of [\cite{Li68}] is to change
equation [\cite{Li68}, (21)] from
\begin{equation}
\frac1Z\mathrm{trace}\left(\prod_{i=1}^N(\lambda+C_i)\right)
\qquad\mathrm{to}\qquad
\frac1Z\mathrm{trace}\left(\prod_{i=1}^N(\ell_i+C_i)\right).
\label{eqreplLi}\end{equation}
The rest of the proof is identical.
\bigskip

\indent If we let all the $\ell_i$'s
equal $z$, then $\mathrm{pf}(A(\bm \ell))$ in~(\ref{eqliebtheo}) is the
polynomial in $z$ whose $2k$-coefficient is the sum of all sub-Pfaffians of
order $2k$. If $a_{i,j}$ is defined as in~(\ref{eqadef}), this {\it seems}
to count all MD coverings with $2k$ monomers: indeed, by Kasteleyn's
theorem, $\mathrm{pf}([a]_{\mathcal I})$ {\it appears} to be the partition
function of dimer coverings of the graph $[g]_{\mathcal I}$ obtained from
$g$ by removing the vertices whose labels are in $\mathcal I$, or
equivalently of MD coverings with monomers on the vertices whose labels are
in $\mathcal I$. This is not the case, however, {\it since $[g]_{\mathcal I}$ is
not necessarily a positive Kasteleyn graph}.

\indent In the rest of this paper, we will provide an algorithm to direct and label
$g$ in such a way that when the vertices in $\mathcal I$ are restricted to
the boundary, which is imposed by setting all other $\ell_i$'s to zero,
$[g]_{\mathcal I}$ is a positive Kasteleyn graph. In that case,
$\mathrm{pf}(A(\bm\ell,\mathbf d))$ is the boundary MD partition function
with $A(\bm\ell,\mathbf d)$ defined in~(\ref{eqpolysta}).
\bigskip

\point{\bf Lower bound on the monomer-dimer partition function.}
When $\mathrm{pf}(A(\bm\ell,\mathbf d))$ does {\it not} equal the MD partition
function, it is so either because the terms in a sub-Pfaffian
$[a(\mathbf d)]_{\mathcal I}$ do not add up constructively, or because the sign of
$\mathrm{pf}([a(\mathbf d)]_{\mathcal I})$ is wrong. Nevertheless, the following
theorem holds.
\bigskip

\theoname{Theorem}{Lower bound for the terms in the MD partition function}\label{theolowerbound}
For every $g\in\mathcal G$, if $d_e\ge0$ for all $e\in\mathcal
E(g)$, then defining
\begin{equation}
 a_{i,j}(\mathbf d):=\left\{
 \begin{array}{l@{\ }l}
  +d_{v_i,v_j}&\mathrm{if\ }\{v_i,v_j\}\in\mathcal E(g)\ \mathrm{and\ }v_i\succ v_j\\
  -d_{v_i,v_j}&\mathrm{if\ }\{v_i,v_j\}\in\mathcal E(g)\ \mathrm{and\ }v_i\prec v_j\\
  0&\mathrm{otherwise}
 \end{array}
 \right.
\label{eqAsimpledef}\end{equation}
in which $v_i$ is a shorthand for $\omega^{-1}(i)$ and, for $i<j$,
\begin{equation}
A_{i,j}(\bm\ell,\mathbf d):=a_{i,j}(\mathbf d)-(-1)^{i+j}\ell_i\ell_j,
\label{eqpolystasimple}\end{equation}
and $A_{j,i}(\bm\ell,\mathbf d):=-A_{i,j}(\bm\ell,\mathbf d)$, the Pfaffian $\mathrm{pf}(A(\bm\ell,\mathbf d))$ is a polynomial in the monomer weights
$\bm\ell$, each of whose coefficients are smaller or equal in absolute value  to the
corresponding term in the MD partition function $\Xi(\bm\ell,\mathbf d)$.
In other words, the coefficient of $\ell_{i_1}\cdots\ell_{i_k}$ is a lower
bound for the number of dimer coverings with monomers at $i_1,\cdots,i_k$.
\endtheo
\bigskip

\point{\bf Proof of corollary \ref{corrmain}.}
Corollary~\ref{corrmain} follows easily from theorems~\ref{theomain} and~\ref{theolieb}. Indeed, by~(\ref{eqtheo}) and~(\ref{eqliebtheo}),
\begin{equation}
M_n(i_1,\cdots,i_{2n})=
\frac{\mathrm{pf}([a(\mathbf d)]_{\mathcal I})}{\mathrm{pf}(a(\mathbf d))}
\label{eqpfM}\end{equation}
with $\mathcal I:=\{i_1,\cdots,i_{2n}\}$. We then make use of the following result: given an invertible $2N\times 2N$ antisymmetric matrix $X$ and a set $s\subset\{1,\cdots,2N\}$ of even cardinality, denoting the sub-matrix of $X^{-1}$ obtained by keeping only the lines and columns  indexed by elements of $s$ by $\{X^{-1}\}_{s}$, we have
\begin{equation}
\frac{\mathrm{pf}([X]_{s})}{\mathrm{pf}(X)}=(-1)^{|s|/2}\mathrm{pf}\{X^{-1}\}_{s},
\label{eqpfminors}\end{equation}
which can easily be proved by block-diagonalizing $X$ via a special unitary transformation, in such a way that each block is a $2\times2$ matrix of the form 
$\left(\begin{array}{cc}0 &\alpha_i\\ -\alpha_i&0\end{array}\right)$. It follows from~(\ref{eqpfminors}) that
\begin{equation}\begin{array}{r@{\ }>{\displaystyle}l}
M_n(i_1,\cdots,i_{2n})=&
(-1)^n\mathrm{pf}(\{a^{-1}(\mathbf d)\}_{\mathcal I})\\[0.3cm]
=&\frac{1}{2^nn!}\sum_{\pi\in\mathcal S_{2n}}(-1)^\pi\prod_{j=1}^n(-a^{-1}(\mathbf d))_{i_{\pi(2j-1)},i_{\pi(2j)}},
\end{array}\label{eqpfMconc}\end{equation}
which concludes the proof, by noting that $(-a^{-1}(\mathbf d))_{i,j}=M_1(i,j)$.
\hfill$\square$





\section{Simple graphs}\label{secsimple}

\indent We shall first consider a family of graphs $\mathcal G_s\subset\mathcal G$,
called \defd{simple graphs}, consisting of a simple, closed circuit of
vertices, which may or may not be connected to each other through edges
inside the circuit (see figure~\ref{figsimpleexample} for an example). All
vertices are therefore part of the circuit, which means that we
are computing the full MD partition function on the graph (with no
restriction on the monomer locations). We denote the
sub-graph of $g$ obtained by removing all internal lines by $\partial g$.
\bigskip

\begin{figure}
\hfil\parbox[m]{3cm}{\includegraphics[width=3cm]{Figs/simple_example.pdf}}
\hfil\parbox[m]{4cm}{\includegraphics[width=4cm]{Figs/bethe.pdf}}\par\penalty10000
\bigskip
\captionshort{Examples of simple graphs. One is a {\it Bethe lattice} built on a
square lattice.}
\label{figsimpleexample}\end{figure}

\indent One way to think about a simple graph is as a special kind of Hamiltonian
graph, i.e., a graph with a closed circuit that visits every vertex exactly
once. Such a graph can be represented as a circuit of
vertices, $\partial g$, 
with connections both external and internal of these vertices. These are
the only vertices, as in our simple graphs, but we impose the additional
constraint on the Hamiltonian graph that all other edges are exclusively
inside or exclusively outside $\partial {g}$. See figure~\ref{fighamiltonianexample} for an example.
\bigskip

\begin{figure}
\hfil\includegraphics[width=5cm]{Figs/comb.pdf}\par\penalty10000
\medskip
\caption{This simple graph can be seen as a sub-graph of the $10\times7$ rectangle, in which we discarded the edges that are on the outside of the grey Hamilton cycle.}
\label{fighamiltonianexample}
\end{figure}

\indent We will now describe how to direct and label a simple graph in such a way that its MD partition function can be written as a Pfaffian as in theorem~\ref{theomain}.
\bigskip

\delimtitleref{Directing and labeling a simple graph}\label{recipesimple}
We label the vertices of $g$ following the edges of $\partial g$
sequentially in the counterclockwise direction
(see figure~\ref{figsimpleexamplelabels} for an example). The resulting
labeling is denoted by $\omega$. The location of the vertex labeled as 1 is
unimportant. The graph is directed by setting $v\succ v'$ if and
only if $\omega(v)<\omega(v')$.
\enddelim
\bigskip

\begin{figure}
\hfil\includegraphics[width=4cm]{Figs/simple_example_labels.pdf}\par\penalty10000
\medskip
\captionshort{The labeling and direction for the first simple graph in
figure~\ref{figsimpleexample}.}
\label{figsimpleexamplelabels}\end{figure}
\bigskip

\indent One readily checks that the resulting
directed graph is Kasteleyn: indeed each minimal circuit, each having
an empty interior, is labeled in an increasing fashion and is thus {\it good}.
In addition, by proposition~\ref{propkasteleyn}, it is positive since
$$
\sigma=\{\big(\omega^{-1}(1),\omega^{-1}(2)\big),\cdots,\big(\omega^{-1}(|g|-1),
\omega^ { -1}(|g|)\big) \}
$$
is a dimer covering of $g$, and its associated permutation is
$\pi_\sigma^{(\omega)}=\mathds1$ (see definition~\ref{defpositivity}).
\bigskip

\indent If the monomers of an MD covering are fixed, the possible dimer
positions are the possible (pure) dimer coverings of the sub-graph of $g$
obtained by removing the vertices that have a monomer. We will now prove
that such a sub-graph is Kasteleyn and positive which implies that the dimer
partition function on it satisfies the Pfaffian
formula~(\ref{eqkasteleyntheo}) which can be substituted
in~(\ref{eqliebtheo}) to reproduce the MD partition function.

\indent Given a family
of monomers $\mathcal M\subsetneq\mathcal V(g)$ of even cardinality, we
define $[g]_{\mathcal M}$ as the sub-graph of $g$ obtained by removing the
vertices in $\mathcal M$ (which may be disconnected), direct the edges of $[g]_{\mathcal M}$ in the same way as those of $g$ (noticing that $\mathcal E([g]_{\mathcal M})\subset\mathcal E(g)$), and define a new labeling $\omega_{\mathcal M}$
for its vertices that is obtained from $\omega$ by removing the monomeric
vertices and eliminating the labeling gaps:
\begin{equation}
\omega_{\mathcal M}(v):=\omega(v)-\mathrm{card}\{v'\in\mathcal M\quad|\quad
\omega(v')<\omega(v)\}.
\label{eqinducedlabeling}\end{equation}
See figure~\ref{figsimpleexamplemonomers} for an
example.
\bigskip

\begin{figure}
\hfil\includegraphics[width=4cm]{Figs/simple_example_monomers.pdf}
\hfil\includegraphics[width=4cm]{Figs/simple_example_auxiliary.pdf}\par\penalty10000
\medskip
\caption{The sub-graph $[g]_{\mathcal M}$ and the auxiliary graph $\gamma_{\mathcal M}$ for the graph in
figure~\ref{figsimpleexamplelabels} with
monomers on the vertices labeled by 1 and 5.}
\label{figsimpleexamplemonomers}\end{figure}
\bigskip

\theo{Lemma}\label{lemmasimplepositivity}
For every $g\in\mathcal G_s$, directed and labeled as above, for all
$\mathcal M\subsetneq\mathcal V(g)$ of even cardinality $|\mathcal M|$, the
sub-graph
$[g]_{\mathcal M}$ whose vertices are labeled by $\omega_{\mathcal M}$ is
Kasteleyn and positive.
\endtheo
\medskip

\indent\underline{Proof}: We prove the lemma by constructing an auxiliary graph
$\gamma_{\mathcal M}$, which is a super-graph of $[g]_{\mathcal M}$ (i.e.
$[g]_{\mathcal M}$ is a sub-graph of $\gamma_{\mathcal M}$), by adding extra
edges in such a way that $\gamma_{\mathcal M}$ is Kasteleyn, and that its
positivity is obvious. The positivity of
$[g]_{\mathcal M}$ then follows from proposition~\ref{propkasteleyn}.

{\bf Remark}: By adding edges to the graph $[g]_{\mathcal M}$ and/or
changing weights, we change the partition function. This, however, is of no
consequence since the extra edges are only used to prove the positivity of
the dimer coverings of $\gamma_{\mathcal M}$ that are {\it also}
coverings of $[g]_{\mathcal M}$ (that is, coverings that do not
use the extra edges), which are the ones of actual interest.

\indent The auxiliary graph $\gamma_{\mathcal M}$ is obtained from $[g]_{\mathcal
M}$ by
\begin{itemize}
\item adding the edge $\{\omega_{\mathcal M}^{-1}(i),\omega_{\mathcal
M}^{-1}(i+1)\}$ for $1\le i\le|[g]_{\mathcal M}|-1$ whenever it is
not present in $[g]_{\mathcal M}$, and directing it from $\omega_{\mathcal
M}^{-1}(i)$ to $\omega_{\mathcal M}^{-1}(i+1)$,
\item adding the edge $\{\omega_{\mathcal M}^{-1}(1),\omega_{\mathcal
M}^{-1}(|[g]_{\mathcal M}|)\}$ if it is not present in $[g]_{\mathcal M}$,
and directing it from $\omega_{\mathcal M}^{-1}(1)$ to $\omega_{\mathcal
M}^{-1}(|[g]_{\mathcal M}|)$.
\end{itemize}
See figure~\ref{figsimpleexamplemonomers} for an example.

\indent This graph is Kasteleyn and positive for the same reason $g$ is (see above).
By definition, this implies that every dimer covering of $\gamma_{\mathcal M}$ is positive, and since $\gamma_{\mathcal M}$ is a super-graph of
$[g]_{\mathcal M}$ and has the same vertices (which are labeled in the same
way), every dimer covering of $[g]_{\mathcal M}$ is a dimer covering of
$\gamma_{\mathcal M}$. This concludes the proof of the lemma.\hfill$\square$
\bigskip

\indent It follows from lemma~\ref{lemmasimplepositivity} and
theorem~\ref{theokasteleyn} that, for $\mathcal M\neq\mathcal V(g)$, by defining $a(\mathbf d)$ as in~(\ref{eqAdef}),
$\mathrm{pf}([a(\mathbf d)]_{\mathcal M})$ is the partition function of dimers on $[g]_{\mathcal M}$.
By theorem~\ref{theolieb}, this implies theorem \ref{theomain} for 
simple graphs, provided $g\in\mathcal G_s$ is directed and labeled as above (see ``\ref{recipesimple}'').

\section{Additional preliminaries}\label{secprelin}
In this section, we discuss several properties which we will use to treat graphs that have vertices inside their boundary.


\subsection{Properties of Kasteleyn graphs}\label{subsecpropkasteleyn}
In this section, we prove a few useful lemmas about Kasteleyn graphs. The key result is the following. 
\bigskip

\theo{Lemma}\label{lemmacombcircuits}
Given two circuits $c_1$ and $c_2$ as in~(\ref{eqmergecircuit}), if $c_1$ and $c_2$ are good then their merger $c=c_1\Delta c_2$ is as well.
\endtheo
\medskip

\indent\underline{Proof}: We write $c_1$ and $c_2$ as in~(\ref{eqmergecircuit}):
$$
c_1=(v_1,\cdots,v_{\nu+1},v_{\nu+2},\cdots,v_{|c_1|}),\quad
c_2=(v_{\nu+1},\cdots,v_{1},v_{\nu+2}',\cdots,v_{|c_2|}')
$$
and
$$
c=(v_{\nu+1},\cdots,v_{|c_1|},v_1,v_{\nu+2}',\cdots,v_{|c_2|}').
$$

\indent We first prove that
\begin{itemize}
\item if $\nu$ is odd, then
  \begin{itemize}
  \item if $c_1$ and $c_2$ are either both oddly-directed or both evenly-directed then $c$ is
oddly-directed,
  \item otherwise $c$ is evenly-directed.
  \end{itemize}
\item if $\nu$ is even, then
  \begin{itemize}
  \item if $c_1$ and $c_2$ are either both oddly-directed or both evenly-directed then $c$ is evenly-directed,
  \item otherwise $c$ is oddly-directed.
  \end{itemize}
\end{itemize}

\indent Indeed, a circuit $c_1$ is oddly-directed if and only if the numbers of backwards edges in
$(v_1,\cdots,v_{\nu+1})$ and in $(v_{\nu+1},\cdots,v_{|c_1|},v_1)$ have
different parity (by which we mean evenness or oddness), and
$c_2$ is oddly-directed if and only if the numbers of backwards edges in
$(v_{\nu+1},\cdots,v_{1})$ and in
$(v_1,v_{\nu+2}',\cdots,v_{|c_2|}',v_{\nu+1})$ have different parity.
Therefore, if $\nu$ is even, using the fact that the numbers of backwards
edges in $(v_1,\cdots,v_{\nu+1})$ and in $(v_{\nu+1},\cdots,v_1)$ have the
same parity, it follows that $c_1\Delta c_2$ is oddly-directed if and only if $c_1$ is
oddly-directed and $c_2$ is evenly-directed or vice-versa. If $\nu$ is odd, the numbers of
backwards edges in $(v_1,\cdots,v_{\nu+1})$ and in $(v_{\nu+1},\cdots,v_1)$
have different parity, so that $c_1\Delta c_2$ is oddly-directed if and only if $c_1$
and $c_2$ are either both oddly-directed or both evenly-directed.
\medskip

\indent The proof of the lemma is then concluded by noticing that
if $\nu$ is odd then the number of vertices that are encircled by either
$c_1$ or $c_2$ has the same parity as the number of vertices encircled by
$c$, whereas the parity is different if $\nu$ is even.\hfill$\square$
\bigskip

\indent Lemma \ref{lemmacombcircuits} has a number of useful consequences, which are discussed in the following. 
\medskip

{\bf Proof of lemma~\ref{lemmakasteleyncomplete}}: Given a circuit $c$ of a Kasteleyn graph $g$, we prove
that it is good by induction on the number of edges it encloses. If it
is a minimal circuit (in particular if it encloses no edge), then it is
good by assumption. If not, then there exist $c_1$ and $c_2$ such that
$c=c_1\Delta c_2$, from which we conclude by the inductive hypothesis and
lemma~\ref{lemmacombcircuits}.\hfill$\square$
\bigskip

\theo{Lemma}\label{lemmakasteleynrmedge}
Given a Kasteleyn graph $g$, the graph obtained by removing any edge of $g$
is Kasteleyn.
\endtheo
\medskip

\indent\underline{Proof}: The lemma follows from lemma~\ref{lemmakasteleyncomplete} and the fact that minimal circuits of the graph obtained by removing the edge are circuits of $g$.\hfill$\square$
\bigskip

\indent We will now prove proposition~\ref{propdirectkasteleyn} and, in the process, provide an algorithm to direct a planar graph $g$ in such a way that the resulting directed graph is Kasteleyn.
\medskip

{\bf Proof of proposition~\ref{propdirectkasteleyn}}: First of all, we notice that we can safely assume that $g$ has a boundary circuit: if it did not, then we construct an auxiliary graph $\gamma$ by adding edges to $g$, as detailed in section~\ref{secboundarycircuit}. Once $\gamma$ has been directed, the extra edges can be removed, and the Kasteleyn nature of the resulting directed graph then follows from lemma~\ref{lemmakasteleynrmedge}.

\indent Assuming $g$ has a boundary circuit, we prove the proposition by induction on the number of
internal edges of the graph.

\indent We first direct the edges of $\partial g$ in such a way that it is good
(if those edges are already directed then $\partial g$ is good by
assumption).

\indent We first consider the case in which $\partial g$ is not a minimal circuit,
in which case there exist $c_1$ and $c_2$ such that $c_1\Delta c_2=c$. We
split $g$ into the graph $g_1$ consisting of $c_1$ and its interior and
$g_2$ consisting of $c_2$ and its interior. We direct the common edges
between $g_1$
and $g_2$ (or equivalently between $c_1$ and $c_2$) in such a
way that $c_1$ is good (there may be many ways of doing so, any one will do). By the inductive hypothesis, this implies that
$g_1$ can be directed appropriately. By lemma~\ref{lemmacombcircuits}, $c_2$
is good, which implies that $g_2$ can be directed as well.

\indent We now turn to the case in which $\partial g$ is a minimal circuit (which
includes the case in which it has no interior edges).

\indent If $\partial g$ encloses no circuit (that is if among the edges $\partial g$
encloses, if any, none form a circuit), then none of the edges enclosed in
$\partial g$ belong to a minimal circuit of $g$ (since that circuit would
have to contain an edge of $\partial g$). Therefore the edges enclosed in
$\partial g$ can be directed in any way without affecting the Kasteleyn
nature of $g$.

\indent If $\partial g$ encloses at least one circuit, let $c_1,\cdots,c_n$ be the
maximal circuits enclosed by $\partial g$. The edges that are outside all of
the $c_i$'s do not belong to any minimal circuit and can therefore be
directed in any way. Let $g_i$ be the sub-graph of $g$ consisting of $c_i$
and its
interior. The sub-graph $g_i$ can be directed by the inductive
hypothesis.\hfill$\square$
\bigskip

\indent We will now discuss the notion of a {\it contraction} of a graph along an edge.
Given a Kasteleyn graph $g\in\mathcal G$ and two vertices $v_0,v_1$ that are connected by an edge that is directed from $v_0$ to $v_1$ ($v_0\succ v_1$), we define the \defd{contraction} $X_{v_0,v_1}g$ of $g$ over $(v_0,v_1)$ in the following way. We denote the family of vertices connected to $v_0$ and $v_1$ respectively, ordered in the {\it clockwise} direction, by $(v_1,u_1,\cdots,u_n)$ and $(v_0,u'_1,\cdots,u'_{n'})$. Let $(u'_{i_1},\cdots,u'_{i_m})\equiv
(u_1'',\ldots,u_m'')$ denote the ordered family obtained from $(u'_1,\cdots,u'_n)$ by removing the vertices that are in $(u_1,\cdots,u_n)$. The contraction $X_{v_0,v_1}g$ is constructed from $g$ by replacing $v_0$ and $v_1$ by a single vertex, which we also denote by $v_0$, connected to $(u_1,\cdots,u_n,u''_{1},\cdots,u''_{m})$ in the {\it clockwise} direction. In other words, the contraction of $g$ is obtained by {\it merging} $v_0$ and $v_1$, contracting the edge $\{v_0,v_1\}$, and removing the resulting double edges. Note that if $v_0\prec v_1$ we do not define the contraction operation $X_{v_0,v_1}g$ at all.

{\bf Remark}: Strictly speaking, the graph $X_{v_0,v_1}g$ has an odd number of vertices and is therefore not an element of $\mathcal G$. This does not matter, since in the following we will always consider an even number of contractions. In the lemma below, the definition of a Kasteleyn graph with an odd number of vertices is identical to definition~\ref{defkasteleyn}.
\bigskip

\theo{Lemma}\label{lemmacontraction}
Consider a Kasteleyn graph $g$ with a boundary circuit $\partial g$ and two vertices $v_0\succ v_1\in\mathcal V(\partial g)$ that are such that $\{v_0,v_1\}\in\mathcal E(\partial g)$, and $v_0$ precedes $v_1$ in the counterclockwise direction. The contraction $X_{v_0,v_1}g$ is Kasteleyn.
\endtheo
\medskip

\indent\underline{Proof}: Using the notation introduced above, consider a circuit $c$ of $X_{v_0,v_1}g$.

\indent If $c$ does not contain $v_0$ or contains $(u_i,v_0,u_j)$ for some $i\neq j$, then it is also a circuit of $g$, and is therefore oddly-directed in $X_{v_0,v_1}g$ if and only if it is oddly-directed in $g$. Since $\{v_0,v_1\}$ is in $\partial g$, the number of vertices encircled by $c$ is the same in $g$ and in 
$X_{v_0,v_1}g$, which implies that $c$ is good.

\indent If $c$ contains $(u''_i,v_0,u''_j)$ for some $i\neq j$, then we define a circuit $c'$ of $g$ by replacing $v_0$ by $v_1$. Again,
$c$ is oddly-directed in $X_{v_0,v_1}g$ if and only if $c'$ is oddly-directed in $g$. Since the number of vertices encircled by $c$  is the same as that by $c'$, we conclude that $c$ is good.

\indent If $c$ contains $(u_i,v_0,u''_j)$ for some $i,j$, then we define a circuit $c'$ of $g$ by replacing $v_0$ by $(v_0,v_1)$. Since $v_0\succ v_1$, $c'$ is oddly-directed if and only if $c$ is oddly-directed which implies, noting again that $c$ and $c'$ encircle the same number of vertices, 
that $c$ is good.

\indent Since $v_0$ precedes $v_1$ in the counterclockwise direction and $c$ is a counterclockwise circuit, $c$ cannot contain $(u''_i,v_0,u_j)$ for any $i,j$.\hfill$\square$
\bigskip

{\bf Remark}: The requirement that $\{v_0,v_1\}$ is on the boundary circuit of $g$ is essential: indeed, if it were not so, one of the following would occur. If $v_0$ and $v_1$ were not both on the boundary, then the number of vertices enclosed by the boundary circuit would change parity when the vertices $v_0$ and $v_1$ were merged, and therefore the boundary circuit would no longer be good. 
If $v_0$ and $v_1$ were both on the boundary but $\{v_0,v_1\}\not\in \mathcal E(\partial g)$, 
then the edge $\{v_0,v_1\}$ would be part of {\it two} circuits, and would appear in one of them as $(u_i,v_0,v_1,u'_j)$ and as $(u'_j,v_1,v_0,u_i)$ in the other. Upon merging $v_0$ and $v_1$, one of the resulting circuits would be good while the other would not.

\subsection{Extended dimer coverings}\label{subsecextendeddimer}

\indent Proving the positivity of a Kasteleyn graph can be difficult: indeed,
one first needs to find a dimer covering of the graph, which is not always
easy (or possible, see figure~\ref{fignoncoverable}). In order to facilitate this task, we define the set of {\it
extended dimer coverings}, show how to construct them for any graph whose connected components have an even number of vertices, and
most importantly, show how to prove the positivity of a graph from one of
its extended dimer coverings.
\bigskip

\begin{figure}
\hfil\includegraphics{Figs/noncoverable.pdf}\par\penalty10000
\medskip
\captionshort{A graph that admits no dimer covering.}
\label{fignoncoverable}
\end{figure}

\indent An \defd{extended dimer covering} of a graph $g$ is a collection of dimers
such that every vertex is covered by an {\it odd} number of dimers (not necessarily by one dimer as is the case for usual dimer
coverings).
See figure~\ref{figextendedcover} for an example.
\bigskip

\begin{figure}
\hfil\includegraphics[width=8cm]{Figs/extended_dimer.pdf}\par\penalty10000
\medskip
\caption{An extended dimer covering: $(1,6)$, $(2,8B)$, $(3,8A)$, $(4,5A)$, $(5C,8C)$, $(7,5B)$. The covering is positive.}
\label{figextendedcover}\end{figure}

\indent One of the nice features of extended dimer coverings is that any connected
graph with an even number of vertices admits at least one extended dimer
covering. This fact is proved in the following proposition, and an algorithm
for constructing an extended dimer covering of a graph is provided in
its proof.
\bigskip

\theo{Proposition}\label{propcovextended}
Given a connected graph $g\in\mathcal G$ (recall that the graphs in $\mathcal G$ have an even number of vertices), $g$ admits at least one extended dimer covering.
\endtheo
\medskip

\indent\underline{Proof}: Let $\mathcal T$ denote a {\it spanning tree} of $g$,
that is a connected sub-graph of $g$ that covers all the vertices of $g$ and
has no loops. We then construct an extended dimer covering of $\mathcal T$,
which, obviously, is also an extended dimer covering of $g$.

\indent We fix one of the vertices of $g$ as the root of $\mathcal T$. We denote the root of $\mathcal T$ by
$v_0$. We construct an extended dimer covering by induction on the {\it
height} of the tree (the height of a vertex $v$ is the number of edges one
needs to traverse to get from $v$ to $v_0$, and the height of a tree is the maximal height of its vertices). 
If the height of $\mathcal
T$ is 1, then we obtain the desired extended dimer covering of $\mathcal T$
by putting a dimer on every edge of $\mathcal T$. If the height $h$ of $\mathcal
T$ is larger than $1$, 
we put a dimer on every edge between a vertex of height $h-1$ and a vertex of height $h$.
We will call these dimers {\it terminal dimers}.
At this point, we let $\mathcal T'$ be the tree obtained by removing from $\mathcal T$ all
the vertices of height $h$ as well as the vertices of height $h-1$ that are touched by an odd number of dimers. 
Note that the height of $\mathcal T'$ is $\le h-1$. By the inductive hypothesis, there exists an extended dimer covering $\sigma'$ of 
$\mathcal T'$. By appending the terminal dimers to $\sigma'$, we obtain an extended dimer covering of $\mathcal T$.
\hfill$\square$
\bigskip

\indent We will now show how to prove positivity from extended dimer coverings.\par
\smallskip
Similarly to dimer coverings, we associate a permutation
$\pi_{\bar\sigma}^{(\omega)}$ to each extended dimer covering $\bar\sigma$. 
We write
\begin{equation}
\bar\sigma=\{(v_1,v_2),\cdots,(v_{|\bar\sigma|-1},v_{|\bar\sigma|})\}
\label{eqbarsigma}\end{equation}
such that $v_{2i-1}\succ v_{2i}$. In this expression the $v_i$'s are
not
necessarily different though they can only appear an {\it odd} number of
times. In addition
to the labeling $\omega(v_i)$, we associate a {\it
letter} $\alpha(v_i)\in\{A,B,\cdots\}$ to $v_i$, in such a way
that when more than one dimer is attached to $v_i$, the letters associated
to these dimers are ordered alphabetically in $\bar\sigma$ in the {\it clockwise} direction.
The permutation
$\pi_{\bar\sigma}^{(\omega)}\in\mathcal S_{|\bar\sigma|}$ is the
permutation that orders $(v_1,\cdots,v_{|\bar\sigma|})$ in {\it
lexicographical order} (e.g. $1A<2A<2B<2C<3A$). The extended dimer
covering $\bar\sigma$ is said to be \defd{positive} if the signature of
$\pi_{\bar\sigma}^{(\omega)}$ is positive. The extended dimer covering in the example in figure~\ref{figextendedcover} is positive.

\indent The analog of proposition~\ref{propkasteleyn} holds for extended dimer
coverings.
\bigskip

\theoname{Proposition}{Uniform positivity for extended dimer coverings}\label{propextendedkasteleyn}
 Given a vertex labeling $\omega$, a Kasteleyn graph $g$ is positive if and
only if one of its extended dimer coverings is positive.
\endtheo
\medskip

\indent\underline{Proof}: The main idea of the proof is to introduce an auxiliary
graph $\gamma$ by adding edges and vertices to $g$ such that every extended
dimer covering of $g$ corresponds uniquely to a usual dimer covering of $\gamma$ that has the same sign $s\in\{-1,1\}$. In addition, $\gamma$ is constructed in
such a way that it is Kasteleyn, which implies that the sign of all of its dimer
coverings is $s$. In particular the sign of the coverings that correspond to
usual dimer coverings of $g$ is $s$ as well.
\medskip

\indent The auxiliary graph $\gamma$ is constructed from $g$ by replacing every
vertex of $g$ by a collection of triangles as in figure~\ref{figtriangles} (see figure~\ref{figextendedcovertriangle} for an example).
It is straightforward to check that there is a one-to-one correspondence between the extended dimer
coverings of a single vertex and the dimer coverings of the
corresponding triangle-replacement (see figure~\ref{figtrianglescovbi}).
This induces a one-to-one mapping between the dimer coverings of
$\gamma$ and the extended dimer coverings of $g$.
\bigskip

\begin{figure}
\hfil
\parbox[m]{2cm}{\includegraphics[width=2cm]{Figs/triangle_3_pre.pdf}}
\hskip20pt$\longmapsto$\hskip20pt
\parbox[m]{2cm}{\includegraphics[width=2cm]{Figs/triangle_3.pdf}}\hskip20pt
\hfil
\parbox[m]{2cm}{\includegraphics[width=2cm]{Figs/triangle_4_pre.pdf}}
\hskip20pt$\longmapsto$\hskip20pt
\parbox[m]{2cm}{\includegraphics[width=2cm]{Figs/triangle_4.pdf}}\par\penalty10000
\bigskip
\hfil
\parbox[m]{2cm}{\includegraphics[width=2cm]{Figs/triangle_5_pre.pdf}}
\hskip20pt$\longmapsto$\hskip20pt
\parbox[m]{2cm}{\includegraphics[width=2cm]{Figs/triangle_5.pdf}}\par\penalty10000
\bigskip
\caption{Replacing vertices with triangles. Only vertices with 3, 4 and 5
edges are drawn, the other cases are treated similarly.}
\label{figtriangles}
\end{figure}
\bigskip

\begin{figure}
\hfil\includegraphics{Figs/extended_dimer_triangle.pdf}\par\penalty10000
\medskip
\caption{The auxiliary graph $\gamma$ corresponding to the graph in figure~\ref{figextendedcover}. The dimer covering associated to the extended dimer covering in figure~\ref{figextendedcover} is represented as well. Its labels are $(1,6)$, $(2,8d)$, $(3,8b)$, $(8c,8a)$, $(4a,4b)$, $(4c,5a)$, $(5e,5c)$, $(5d,8g)$, $(8e,8f)$, $(7,5b)$.}
\label{figextendedcovertriangle}
\end{figure}

\begin{figure}
\hfil
\parbox[m]{2cm}{\includegraphics[width=2cm]{Figs/triangle_3_Xcover1.pdf}}
\hskip20pt$\longmapsto$\hskip20pt
\parbox[m]{2cm}{\includegraphics[width=2cm]{Figs/triangle_3_cover1.pdf}}\hskip20pt
\hfil
\parbox[m]{2cm}{\includegraphics[width=2cm]{Figs/triangle_3_Xcover3.pdf}}
\hskip20pt$\longmapsto$\hskip20pt
\parbox[m]{2cm}{\includegraphics[width=2cm]{Figs/triangle_3_cover3.pdf}}\par\penalty10000
\bigskip
\caption{Bijection between the set of extended dimer coverings of a vertex and the set of dimer coverings of its triangle-replacement. The case with 3 external lines is drawn, the others are treated similarly.}
\label{figtrianglescovbi}
\end{figure}


\indent The extra triangles in $\gamma$ are directed as per
figure~\ref{figtriangledirect}. We now show that $\gamma$ is Kasteleyn. Each
triangle is a minimal circuit of $\gamma$ and is good. In any other
minimal circuit containing an edge of a triangle, that edge will be {\it
forwards}, which implies that the
circuit is good if and only if the corresponding circuit in $g$ is
good as well. This proves that $\gamma$ is Kasteleyn.
\bigskip

\begin{figure}
\hfil\includegraphics{Figs/triangle_5_directed.pdf}\par\penalty10000
\medskip
\caption{The direction and labeling of the extra triangles in $\gamma$. The
example for 5 external edges is shown, the others are treated similarly.}
\label{figtriangledirect}
\end{figure}


\indent Finally, we show that an extended dimer covering of $g$ is positive if and only if the
corresponding dimer covering of $\gamma$ is positive. To do so, we label
the vertices of $\gamma$ in the following way. In order to simplify the
discussion, the label of a vertex in $\gamma$ will be a number and a letter
instead of just a number. Given a vertex $v$ in $g$ labeled by $\omega(v)$,
the number in the label of each vertex of the corresponding
triangle-replacement in $\gamma$ is set to $\omega(v)$. The letters of the
labels of the vertices in each triangle-replacement are assigned as per
figure~\ref{figtriangledirect}. Note that the external lines in
figure~\ref{figtriangledirect} are labeled alphabetically in the {\it
clockwise} direction, as were the dimers in~(\ref{eqbarsigma}).

\indent Consider a dimer covering $\sigma$ of $\gamma$ and its associated
extended dimer covering $\bar\sigma$ of $g$. There are two types of dimers
in $\sigma$: {\it internal} dimers which cover an edge of one of the extra
triangles, and {\it external} dimers. Internal dimers are labeled as
$(x\alpha,x\alpha')$ with $x\alpha\succ x\alpha'$, where $x\in\mathbb N$ is the number-label corresponding
to the triangle that contains it and $\alpha,\alpha'\in\{a,b,\cdots\}$ are
the letter-labels of its extremities, while external dimers are labeled as $(x\alpha,y\alpha')$ with $x\alpha\succ y\alpha'$, where $x\neq y$ are the number-labels corresponding to the triangles that its extremities are connected to and $\alpha,\alpha'$ are the letter-labels corresponding to its extremities.

\indent We write the dimer covering $\sigma$ as an ordered collection of labels
$$
\sigma=(x_1\alpha_1,x_2\alpha_2,\cdots,x_{|\gamma|}\alpha_{|\gamma|})
$$
in which the dimers of $\sigma$ are $(x_{2i-1}\alpha_{2i-1},x_{2i}\alpha_{2i})$. Similarly, we write $\bar\sigma$ as
$$
\bar\sigma=(y_1\beta_1,y_2\beta_2,\cdots,y_{|\bar\sigma|}\beta_{|\bar\sigma|}).
$$
With no loss of generality, we assume that the labels of the vertices covered by external dimers
appear in the same order both in $\sigma$ and in $\bar\sigma$.

\indent The claim of the proposition is that $\sigma$ can be ordered by a positive-signature permutation if and only if $\bar\sigma$ can be. In order to prove this, we will {\it group} some labels in $\sigma$ together and label the groups in such a way that $\sigma$, written in terms of its groups, has a similar expression as $\bar\sigma$. 

\indent We denote the set of labels of vertices covered by external dimers of $\sigma$ by $\epsilon(\sigma)$. Given a 
number-label $x$, we let $\iota_x(\sigma)=\{\beta\,:\,x\beta$ is covered by an internal dimer of $\sigma\}$.
In addition, given one of the extra triangles in $\gamma$ and two of its vertices, with letter-labels $\beta,\beta'$, we denote the letter-label of the third vertex of the triangle by $\tau_{\beta,\beta'}$ (e.g., $\tau_{b,c}=a$ and $\tau_{c,e}=d$, see figure~\ref{figtriangledirect}).
For every $x\alpha\in \epsilon(\sigma)$ we define an ordered set 
$x\bar\alpha$ containing $x\alpha$ and the labels $x\beta\in\iota_x(\sigma)$, which are such that,
if $(x\beta,x\beta')$ is a dimer and $x\beta,x\beta'\in x\bar\alpha$, then $x\tau_{\beta,\beta'}\in x\bar\alpha$. The ordering of $x\bar\alpha$ 
is that inherited from $\sigma$. The set $x\bar\alpha$ can either be {\it trivial}, if it has only one element (in which case $x\bar\alpha=(x\alpha)$),
or it can be of three possible non-trivial types, depicted in figure~\ref{fig:4.7}.

\indent In all cases, $x\bar\alpha$ is, up to a positive-signature permutation, 
of the form
$$x\bar\alpha=(x[\alpha-k],\ldots,x\alpha,\ldots, x[\alpha+k']),$$
where $k,k'\ge 0$, $k+k'$ is even and $[\alpha+i]$ is the character-wise addition (e.g., $[a+2]=c$ and $[j-6]=d$). 
\bigskip

\begin{figure}
\hfil\includegraphics[width=8cm]{Figs/triangle_groups_lr.pdf}\par\penalty10000
\bigskip
\hfil\includegraphics[width=6cm]{Figs/triangle_groups_l.pdf}
\hfil\includegraphics[width=6cm]{Figs/triangle_groups_r.pdf}\par\penalty10000
\bigskip
\caption{The three possible types of non-trivial sets $x\bar\alpha$, and their corresponding dimer covering. In each of these, the labels of the vertices covered by dimers can be written as $(x[\alpha-k],\ldots,x\alpha,\ldots, x[\alpha+k'])$. In the first case, $k,k'$ are both odd. In the second case, 
$k$ is positive and even, while $k'=0$. In the third case, $k=0$, while $k'$ is positive and even.
In addition to these types, $x\bar\alpha$ could be trivial, that is $k=k'=0$.}
\label{fig:4.7}
\end{figure}

\indent In addition, it is straightforward to check that, by a permutation that rigidly moves the labels of pairs of vertices covered by the same dimer, $\sigma$ can be turned into
$$
\sigma'\equiv(y_1\bar\alpha_1,\cdots,y_{|\bar\sigma|}\bar\alpha_{|\bar\sigma|})
$$
where the $y_i$'s are the same, and are ordered in the same way, as in $\bar\sigma$.
Note that, since the sets $y_i\bar\alpha_i$ have odd cardinality and contain ordered sequences of labels, the permutation that orders $\sigma$ and the permutation that orders $\sigma'$ have the same signature. We are therefore left with proving that this permutation has the same signature as that which orders $\bar\sigma$.

\indent The indices $\alpha_i$ associated with the indices $\bar\alpha_i$ in $\sigma'$ are not equal, in general, to the indices $\beta_i$ in $\bar\sigma$. However, 
they appear in the same order as the $\beta_i$'s, i.e. if $y\bar\alpha_i$ and $y\bar\alpha_j$ (resp.
$y\beta_i$ and $y\beta_j$) appear in $\sigma'$ (resp. $\bar\sigma$) in that order, 
then $\alpha_i<\alpha_j$ if and only if $\beta_i<\beta_j$. Indeed, restricting our attention to the elements that share the same number-label $y$:
$$
y\bar\alpha_{i_1},\cdots,y\bar\alpha_{i_k}\qquad\mathrm{and}\qquad
y\beta_{i_1},\cdots,y\beta_{i_k}
$$
we notice that the permutations that order these sequences in the lexicographic order, 
also order the vertices in the
clockwise direction. Therefore, the $y\bar\alpha_i$'s can be ordered by the same permutation as the $y\beta_i$'s, which concludes the proof of the proposition.\hfill$\square$


\section{Evenly filled graphs}\label{seceven}

\indent We will now delve into the next level of complexity and consider graphs
with interior edges and vertices. For the time being, we require that every
connected component of the graph formed by the interior edges and vertices
has an even number of vertices. The general case will be discussed in the
next section.
\bigskip

\indent The family of \defd{evenly filled graphs} $\mathcal G_e\subset\mathcal G$ is
defined
in the following way. Evenly filled graphs are connected and consist of an
interior
graph $\check g\in\mathcal G$ each of whose connected components contains an
even number of vertices, enclosed
within a boundary circuit of vertices $\partial g$. Since evenly filled graphs are
connected, $\partial g$ must be connected to each connected component of
$\check g$ by at least one
edge. In addition, vertices of $\partial g$ may be connected to each other
by internal edges. See figure~\ref{figevenexample} for an example. Note that $\mathcal G_s\subset\mathcal G_e\subset\mathcal G$.
\hugeskip

\begin{figure}
\hfil\includegraphics{Figs/even_example.pdf}\par\penalty10000
\medskip
\captionshort{An evenly filled graph.}
\label{figevenexample}
\end{figure}

\indent We will now describe how to direct and label an evenly filled graph in such a way that its boundary MD partition function can be written as a Pfaffian as in theorem~\ref{theomain}.
\bigskip

\delimtitleref{Directing and labeling an evenly filled graph}\label{recipeeven}
We label the vertices of $\partial g$ by following the edges of $\partial g$ sequentially in the counterclockwise direction. The resulting labeling is denoted by $\omega$. The location of
the vertex labeled as 1 is unimportant. 

\indent We then direct the edges of $\partial g$:
$\omega^{-1}(i)\succ\omega^{-1}(i+1)$ and
$\omega^{-1}(1)\succ\omega^{-1}(|\partial g|)$. This implies that
$\partial g$ is good so that the remaining edges of
$g$ can be directed by
proposition~\ref{propdirectkasteleyn}. We arbitrarily choose one of the directions  constructed in its proof, see section \ref{subsecpropkasteleyn}.

\indent Finally, we label the remaining vertices: we consider an extended dimer
covering of $\check g$, which exists by proposition~\ref{propcovextended},
and set the labels in such a way that this covering is positive. In order to
construct such a labeling, one can pick a random labeling of the vertices,
check whether the extended dimer covering is positive, and exchange two
labels if it is not.
\enddelim
\bigskip
See figure~\ref{figevenexamplelabels} for an example.
\bigskip

\begin{figure}
\hfil\includegraphics{Figs/even_example_label_pre.pdf}
\hfil\includegraphics{Figs/even_example_label.pdf}\par\penalty10000
\medskip
\caption{Two stages of the directing and labeling of the graph in figure~\ref{figevenexample}. The first represents $g$ after having labeled $\partial g$. The second shows an extended dimer covering (which happens to be a usual dimer covering) of $\check g$ and an associated labeling. The labels are chosen in such a way that this covering is positive: $(13,14)$, $(15,16)$.}
\label{figevenexamplelabels}
\end{figure}

\indent Thus directed, the graph $g$ is Kasteleyn. We now prove that it is positive by constructing an extended dimer covering of the entire graph $g$ by combining the extended dimer covering of $\check g$ mentioned above and the boundary-dimers
$$
\{(\omega^{-1}(1),\omega^{-1}(2)),\cdots,(\omega^{-1}(|\partial g|-1),\omega^{-1}(|\partial g|))\}.
$$
Since the boundary-dimers are labeled sequentially, this covering is positive, which implies that $g$ is positive as well. See figure~\ref{figevenexamplecover} for an example.
\bigskip

\begin{figure}
\hfil\includegraphics{Figs/even_example_cover.pdf}\par\penalty10000
\medskip
\caption{An extended dimer covering of the graph in figure~\ref{figevenexample} with the labeling of figure 
\ref{figevenexamplelabels}
(which happens to be a usual dimer covering). The covering can be labeled as
$(1,2)$, $(3,4)$, $(5,6)$, $(7,8)$, $(9,10)$, $(11,12)$, $(13,14)$ and its associated permutation is the identity.}
\label{figevenexamplecover}
\end{figure}

\indent If the monomers of an MD covering are fixed on vertices of $\partial
g$, the possible dimer
positions are the possible (pure) dimer coverings of the sub-graph of $g$
obtained by removing the vertices that have a monomer. We will now prove
that such a sub-graph is Kasteleyn and positive which implies that the dimer
partition function on it satisfies the Pfaffian
formula~(\ref{eqkasteleyntheo}) which can be substituted
in~(\ref{eqliebtheo}) to reproduce the MD partition function.

\indent Given a family
of monomers $\mathcal M\subset\mathcal V(\partial g)$ of even cardinality,
we
define $[g]_{\mathcal M}$ as the sub-graph of $g$ obtained by removing the
vertices in $\mathcal M$, and define a new labeling $\omega_{\mathcal M}$
for its vertices that is obtained from $\omega$ by removing the monomeric
vertices and eliminating the labeling gaps:
\begin{equation}
\omega_{\mathcal M}(v):=\omega(v)-\mathrm{card}\{v'\in\mathcal M\quad|\quad
\omega(v')<\omega(v)\}.
\label{eqinducedlabelingeven}\end{equation}
See figure~\ref{figevenexamplemonomer} for an example. Note that this definition is ill-posed if $[g]_{\mathcal M}$ is empty (i.e. if $g$ does not have interior vertices and $\mathcal M=\mathcal V(g)$), but this is of little consequence.

\begin{figure}
\hfil\includegraphics{Figs/even_example_monomer.pdf}
\hfil\includegraphics{Figs/even_example_auxiliary.pdf}\par\penalty10000
\medskip
\caption{The sub-graph $[g]_{\mathcal M}$ and the auxiliary graph $\gamma_{\mathcal M}$ for the graph in
figure~\ref{figevenexamplelabels} with
monomers on the vertices labeled by 1, 8, 10 and 12.}
\label{figevenexamplemonomer}\end{figure}
\bigskip

\theo{Lemma}\label{lemmaevenpositivity}
For every $g\in\mathcal G_e$, directed and labeled as above, for all
$\mathcal M\subset\mathcal V(\partial g)$ of even cardinality $|\mathcal
M|$, the sub-graph
$[g]_{\mathcal M}$ whose vertices are labeled by $\omega_{\mathcal M}$ is
Kasteleyn and positive.
\endtheo
\medskip

\indent\underline{Proof}: We first notice that $[g]_{\mathcal M}$ is Kasteleyn
because, since the monomers are on $\partial g$, the minimal circuits of
$[g]_{\mathcal M}$ are minimal circuits of $g$. In order to prove its
positivity, we construct an auxiliary graph
$\gamma_{\mathcal M}$, which is a super-graph of $[g]_{\mathcal M}$ (i.e.
$[g]_{\mathcal M}$ is a sub-graph of $\gamma_{\mathcal M}$), by adding extra
edges in such a way that $\gamma_{\mathcal M}$ is Kasteleyn, and that its
positivity is obvious. The positivity of
$[g]_{\mathcal M}$ then follows from proposition~\ref{propkasteleyn}. 

\indent In order to define $\gamma_{\mathcal M}$, we first define the sub-graph $\eta_{\mathcal M}$ of $g$ obtained by removing the edges that are connected to vertices in $\mathcal M$ and are not in $\mathcal E(\partial g)$. In other words, $\eta_{\mathcal M}$ is the union of $[g]_{\mathcal M}$ and $\partial g$. 
It follows from lemma~\ref{lemmakasteleynrmedge} that $\eta_{\mathcal M}$ is Kasteleyn. For every vertex $v\in\mathcal M$, we define the vertex $u(v)$ in the following way:
\begin{itemize}
\item if the set $\{\omega(v')\ |\ v'\in\mathcal V(\partial g)\setminus\mathcal M,\ \omega(v')<\omega(v)\}$ is not empty, then $\omega(u(v))$ is its maximizer.
\item if the set is empty, then $\omega(u(v))$ is the minimizer of $\{\omega(v')\ |\ v'\in\mathcal V(\partial g)\setminus\mathcal M,\ \omega(v')>\omega(v)\}$.
\end{itemize}
Note that $u(v)$ is separated from $v$ on $\partial g$ only by vertices in $\mathcal M$ and edges that are $\neq\{\omega^{-1}(1),$ $\omega^{-1}(|\partial g|)\}$. 
Note also that in general there might be $v_1\neq v_2$ such that $u(v_1)=u(v_2)$. Given this notion, 
$\gamma_{\mathcal M}$ is defined as the {\it contraction} $$\big(\prod_{\mAthop{v\in\mathcal M}_{u(v)\prec v}}X_{u(v),v}
\prod_{\mAthop{v\in\mathcal M}_{u(v)\succ v}}X_{v,u(v)}\big)\eta_{\mathcal M},$$ 
where the $X_{u(v),v}$ should be multiplied in an order such that the product is well defined (see figure~\ref{figevenexamplemonomer} for an example).

\indent Thus defined, $\gamma_{\mathcal M}$ is a super-graph of $[g]_{\mathcal M}$, and, because of the way $\omega$ and $u(v)$ were defined, the edges that are contracted are all directed in the {\it counterclockwise} direction, which allows us to apply lemma~\ref{lemmacontraction} to prove that $\gamma_{\mathcal M}$ is Kasteleyn.

\indent We are left with proving that $\gamma_{\mathcal M}$ is positive. Because of the way the labeling $\omega_{\mathcal M}$ was defined, the dimer
covering corresponding to the identity-permutation restricted to the boundary of $\gamma_{\mathcal M}$ is an acceptable dimer covering. The interior of $\gamma_{\mathcal M}$ is the same as the interior of $g$, and can therefore be covered by the same extended dimer covering as $\check g$. Therefore, $\gamma_{\mathcal M}$ is positive. See figure~\ref{figevenexampleauxcover} for an example.\hfill$\square$
\bigskip

\begin{figure}
\hfil\includegraphics{Figs/even_example_auxcover.pdf}\par\penalty10000
\medskip
\caption{An extended dimer covering of $\gamma_{\mathcal M}$ (which happens to be a usual dimer covering).}
\label{figevenexampleauxcover}
\end{figure}

\indent It follows from lemma~\ref{lemmaevenpositivity} and
theorem~\ref{theokasteleyn} that by defining $a(\mathbf d)$ as in~(\ref{eqAdef}),
$\mathrm{pf}([a(\mathbf d)]_{\mathcal M})$ is the partition function of dimers on $[g]_{\mathcal M}$,
which, by theorem~\ref{theolieb}, implies 
theorem \ref{theomain} for evenly filled graphs, provided $g\in\mathcal G_e$ is directed and labeled as above (see ``\ref{recipeeven}'').


\section{Enclosed graphs}\label{secenclosed}

\indent We now turn to the more general case of graphs that have a boundary circuit.
\bigskip

\indent The family of \defd{enclosed graphs} $\mathcal G_{en}\subset\mathcal G$ is
defined
in the following way. Enclosed graphs are connected and consist of an
interior
graph $\check g\in\mathcal G$ enclosed
within a boundary circuit of vertices $\partial g$ containing an {\it even} number $|\partial g|$ of vertices. Since enclosed graphs are
connected, $\partial g$ must be connected to each connected component of
$\check g$ by at least one
edge. In addition, vertices of $\partial g$ may be connected to each other
by internal edges. See figure~\ref{figenclosedexample} for an example. Note that since $|g|$ is even, $|\check g|$ is even as well. Notice that $\mathcal G_s\subset\mathcal G_e\subset\mathcal G_{en}\subset\mathcal G$.
\bigskip

\begin{figure}
\hfil\includegraphics[width=6cm]{Figs/enclosed_example.pdf}\par\penalty10000
\medskip
\captionshort{An enclosed graph.}
\label{figenclosedexample}\end{figure}

\indent We will now describe how to direct and label an enclosed graph in such a way that its boundary MD partition function can be written as a Pfaffian as in theorem~\ref{theomain}. See figure~\ref{figenclosedexamplecover} for an example.
\bigskip

\delimtitleref{Directing and labeling an enclosed graph}\label{recipeenclosed}
We first label the vertices of $\partial g$ following the edges of $\partial g$ sequentially in the counterclockwise direction. The resulting labeling is denoted by $\omega$. The location of the vertex labeled as 1 is unimportant.

\indent We then direct the edges of $\partial g$:
$\omega^{-1}(i)\succ\omega^{-1}(i+1)$ and $\omega^{-1}(1)\succ\omega^{-1}(|\partial g|)$.
This implies that $\partial g$ is good. The
remaining edges of $g$ can be directed by
proposition~\ref{propdirectkasteleyn}. We arbitrarily choose one of the directions  constructed in its proof, see section \ref{subsecpropkasteleyn}.

\indent Finally, we label the remaining vertices by constructing an extended dimer
covering of $g$ and requiring that it
be positive. By
proposition~\ref{propcovextended}, such a covering exists. We choose $\omega$ by picking a random labeling of the vertices, checking whether the extended dimer
covering is positive, and exchanging two labels if it is not.
\enddelim
\bigskip

\begin{figure}
\hfil\includegraphics[width=6cm]{Figs/enclosed_example_directed.pdf}
\hfil\includegraphics[width=6cm]{Figs/enclosed_example_cover.pdf}\par\penalty10000
\medskip
\caption{Two stages of the directing and labeling of the graph in figure~\ref{figenclosedexample}. The first represents $g$ after having labeled the vertices of $\partial g$. The second shows an extended dimer covering of $g$ and an associated labeling. The labels are chosen in such a way that this covering is positive:
$(1,2)$, $(3,4B)$, $(4A,5)$, $(7,8A)$, $(8B,4C)$, $(10,8C)$ $(6,9)$, $(11,12)$, $(13,14A)$, $(14B,15)$, $(16,14C)$.}
\label{figenclosedexamplecover}\end{figure}


\indent If the monomers of an MD covering are fixed on vertices of $\partial
g$, the possible dimer
positions are the possible (pure) dimer coverings of the sub-graph of $g$
obtained by removing the vertices that have a monomer. We will now prove
that such a sub-graph is Kasteleyn and positive which implies that the dimer
partition function on it satisfies the Pfaffian
formula~(\ref{eqkasteleyntheo}) which can be substituted
in~(\ref{eqliebtheo}) to reproduce the MD partition function.

\indent Given a family
of monomers $\mathcal M\subset\mathcal V(\partial g)$ of even cardinality,
we
define $[g]_{\mathcal M}$ as the sub-graph of $g$ obtained by removing the
vertices in $\mathcal M$, and define a new labeling $\omega_{\mathcal M}$
for its vertices that is obtained from $\omega$ by removing the monomeric
vertices and eliminating the labeling gaps:
\begin{equation}
\omega_{\mathcal M}(v):=\omega(v)-\mathrm{card}\{v'\in\mathcal M\quad|\quad
\omega(v')<\omega(v)\}.
\label{eqinducedlabelingenclosed}\end{equation}
See figure~\ref{figetareplace2} for an example.
\bigskip

\theo{Lemma}\label{lemmaenclosedpositivity}
For every $g\in\mathcal G_{en}$, directed and labeled as above, for all
$\mathcal M\subset\mathcal V(\partial g)$ of even cardinality $|\mathcal
M|$, the sub-graph
$[g]_{\mathcal M}$ whose vertices are labeled by $\omega_{\mathcal M}$ is
Kasteleyn and positive.
\endtheo
\medskip

\indent\underline{Proof}: We first notice that $[g]_{\mathcal M}$ is Kasteleyn
because, since the monomers are on $\partial g$, the minimal circuits of
$[g]_{\mathcal M}$ are minimal circuits of $g$. In order to prove its
positivity, we will first construct an auxiliary graph $\varphi$ by adding edges and vertices to $g$, which is evenly filled. We will then show that $[g]_{\mathcal M}$ is positive if and only if $[\varphi]_{\mathcal M}$ is, by constructing an injective map $\lambda_{\varphi,\mathcal M}$ from the set of extended dimer coverings of $[g]_{\mathcal M}$ to those of $[\varphi]_{\mathcal M}$ that preserves positivity. 
Finally, using the fact that $\varphi$ is evenly filled and lemma \ref{lemmaevenpositivity} we conclude that $[\varphi]_{\mathcal M}$ is positive.
\medskip

\indent We construct $\varphi$ from $g$ in the following way. Consider $\check g$. We add as many edges as needed to connect the connected components of $\check g$ to each other. Some of these extra edges may cross edges of $g$. We replace every such crossing as per figure~\ref{figetareplace}. Note that by this construction, some edges may be crossed multiple times (this could be avoided by choosing the edges to add to $\check g$ carefully, but it is not necessary to do so).
\bigskip

\begin{figure}
\hfil\parbox[m]{4cm}{\includegraphics[width=4cm]{Figs/etareplace_cross.pdf}}
\hfil$\longmapsto$
\hfil\parbox[m]{4cm}{\includegraphics[width=4cm]{Figs/etareplace_r.pdf}}\par\penalty10000
\medskip
\caption{Replacing a crossing in the construction of $\varphi$. The solid line is the edge that is in $\mathcal E(g)$, and the dotted line is the extra edge that was added to $\varphi$ in order to connect $\check g$.}
\label{figetareplace}\end{figure}

\indent The edges of $\varphi$ are directed in the following way. First of all, the edges in $\mathcal E(\varphi)\cap\mathcal E(g)$ are directed in the same way as in $g$. Next, the edges in $\mathcal E(\varphi)\setminus\mathcal E(g)$ corresponding to the solid lines in figure~\ref{figetareplace}
are directed as shown there. The circuits containing such edges are good, since the parity of the number of backwards edges is unchanged by the replacement. Finally, we direct the remaining edges in $\varphi$ by using the proof proposition~\ref{propdirectkasteleyn}.

\indent We introduce the following notation: given an edge $e=\{v,v'\}\in\mathcal E(g)\setminus\mathcal E(\varphi)$, that is, an edge of $g$ that was replaced when removing edge crossings, if $v\succ v'$, then we define $(v,$ $\chi_1(e),\cdots,\chi_{2s_e}(e),$ $v')$ as the ordered string of vertices that replaces $e$.

\indent The vertex labeling $\omega_\varphi$ of $\varphi$ is defined in the following way. The vertices $v$ in $\mathcal V(\varphi)\cap\mathcal V(g)$ are labeled in the same way as in $g$: $\omega_\varphi(v):=\omega(v)$. The pairs $(\chi_{2i-1}(e),\chi_{2i}(e))$ of vertices that were added to $\varphi$ by replacing a crossing are labeled in such a way that $\omega_\varphi(\chi_{2i}(e))=\omega_\varphi(\chi_{2i-1}(e))+1$ and $\omega_\varphi(\chi_{2i-1}(e))>|g|$.
\medskip

\indent We now construct an injective mapping $\lambda_{\varphi,\mathcal M}$ from the extended dimer coverings of $[g]_{\mathcal M}$ to those of $[\varphi]_{\mathcal M}$ and show that $\lambda_{\varphi,\mathcal M}$ preserves positivity. Given an extended dimer covering $\sigma$ of $[g]_{\mathcal M}$, we construct an extended dimer covering $\lambda_{\varphi,\mathcal M}(\sigma)$ of $[\varphi]_{\mathcal M}$ in the following way. We first add the dimers of $\sigma$ that occupy an edge that is in $\mathcal E([g]_{\mathcal M})\cap\mathcal  E([\varphi]_{\mathcal M})$ to $\lambda_{\varphi,\mathcal M}(\sigma)$.
\begin{itemize}
\item If an edge $e=\{v,v'\}\in\mathcal E([g]_{\mathcal M})\setminus\mathcal E([\varphi]_{\mathcal M})$ with $v\succ v'$ is occupied by a dimer, then we add the dimers $\{v,\chi_{1}(e)\}$, $\{\chi_{2i}(e),\chi_{2i+1}(e)\}$ for $1\le i\le s_e-1$, $\{\chi_{2s_e}(e),v'\}$ to $\lambda_{\varphi,\mathcal M}(\sigma)$.
\item If an edge $e=\{v,v'\}\in\mathcal E([g]_{\mathcal M})\setminus\mathcal E([\varphi]_{\mathcal M})$ with $v\succ v'$ is not occupied by a dimer, then we add the dimers $\{\chi_{2i-1}(e),\chi_{2i}(e)\}$ for $1\le i\le s_e$, to $\lambda_{\varphi,\mathcal M}(\sigma)$.
\item Similarly, for every edge $e=\{v,v'\}\in\left(\mathcal E(g)\setminus\mathcal E(\varphi)\right)\setminus\mathcal E([g]_{\mathcal M})$ with $v\succ v'$ (i.e. every edge that is in $g$, not in $\varphi$, and has at least one endpoint in $\mathcal M$), we add the dimers $\{\chi_{2i-1}(e),\chi_{2i}(e)\}$ for $1\le i\le s_e$, to $\lambda_{\varphi,\mathcal M}(\sigma)$.
\end{itemize}
See figures~\ref{figetareplaceocc}, \ref{figetareplace1} and~\ref{figetareplace2} for examples.
\bigskip

\begin{figure}
\hfil\includegraphics[width=4cm]{Figs/etareplace_occupied.pdf}
\hfil\includegraphics[width=4cm]{Figs/etareplace_empty.pdf}\par\penalty10000
\medskip
\caption{Covering of the replacement edges of $\varphi$. Left: the corresponding edge in $g$ is occupied. Right: the corresponding edge in $g$ is not occupied.}
\label{figetareplaceocc}\end{figure}

\begin{figure}
\hfil\includegraphics[width=6cm]{Figs/enclosed_example_auxiliary_cover.pdf}\par\penalty10000
\medskip
\captionshort{The covering of the auxiliary graph $\varphi$ corresponding to the covering in figure~\ref{figenclosedexamplecover}.}
\label{figetareplace1}\end{figure}
\bigskip

\begin{figure}
\hfil\includegraphics[width=6cm]{Figs/enclosed_example_monomer_cover.pdf}
\hfil\includegraphics[width=6cm]{Figs/enclosed_example_monomer_auxiliary_cover.pdf}\par\penalty10000
\medskip
\caption{The sub-graph $[g]_{\{6,8\}}$, one of its extended dimer coverings, and the corresponding covering of $[\varphi]_{\{6,8\}}$.}
\label{figetareplace2}\end{figure}

\indent We now prove that $\sigma$ is positive if and only if $\lambda_{\varphi,\mathcal M}(\sigma)$ is. We write $\sigma$ as an ordered sequence of vertices $(v_1,\cdots,v_{2n})$ in which the dimers occupy $\{v_{2i-1},v_{2i}\}$ with $v_{2i-1}\succ v_{2i}$. By construction, $\lambda_{\varphi,\mathcal M}(\sigma)$ is obtained from $\sigma$ by
\begin{itemize}
\item replacing $(v,v')$, in which $e=\{v,v'\}\in\mathcal E([g]_{\mathcal M})\setminus\mathcal E([\varphi]_{\mathcal M})$, by $(v,\chi_1(e),$ $\cdots,\chi_{2s_e}(e),v')$,
\item adding $(\chi_1(e),\cdots,\chi_{2s_e}(e))$ to $\sigma$ for every $e\in\mathcal E([g]_{\mathcal M})\setminus\mathcal E([\varphi]_{\mathcal M})$ that is not occupied by a dimer, and for every $e\in\left(\mathcal E(g)\setminus\mathcal E(\varphi)\right)\setminus\mathcal E([g]_{\mathcal M})$.
\end{itemize}
Since $\omega_{\varphi}(\chi_{2i}(e))=\omega_{\varphi}(\chi_{2i-1}(e))+1$, the $\omega_{\varphi}(\chi_i(e))$ labels can be ordered and moved after the vertices of $\mathcal V([g]_{\mathcal M})$ by a positive-signature permutation. Furthermore, the vertices of $\mathcal V([g]_{\mathcal M})$ can be ordered by a positive-signature permutation if and only if $\sigma$ is positive. Since $\omega_{\varphi}(\chi_{i}(e))>|g|$, this implies that $\sigma$ is positive if and only if $\lambda_{\varphi,\mathcal M}(\sigma)$ is.
\medskip

\indent Now note that $\varphi$ is an evenly filled graph, whose direction and labeling is compatible with the recipe given in section \ref{seceven} (see ``\ref{recipeeven}''). 
It therefore follows from lemma \ref{lemmaevenpositivity} that 
$[\varphi]_{\mathcal M}$ is positive. Moreover, the image of any extended dimer covering of $[g]_{\mathcal M}$ through $\lambda_{\varphi,\mathcal M}$ is positive, which implies that the extended dimer covering itself is positive, and therefore that $[g]_{\mathcal M}$ is as well.\hfill$\square$
\bigskip

\indent It follows from lemma~\ref{lemmaenclosedpositivity} and
theorem~\ref{theokasteleyn} that by defining $a(\mathbf d)$ as in~(\ref{eqAdef}),
$\mathrm{pf}([a(\mathbf d)]_{\mathcal M})$ is the partition function of dimers on $[g]_{\mathcal M}$,
which, by theorem~\ref{theolieb}, implies 
theorem \ref{theomain} for enclosed graphs, provided $g\in\mathcal G_{en}$ is directed and labeled as above (see ``\ref{recipeenclosed}'').

\section{Reducing generic planar graphs to enclosed graphs}\label{sec7}
In this section, we discuss how a generic planar graph can be reduced to an enclosed graph. In particular, we will show how to add 0-weight edges to a graph to construct a boundary circuit, and how to add 0-weight edges and vertices to a graph that has an odd number of vertices in its boundary circuit to turn it into an enclosed graph, for which theorem~\ref{theomain} was proved in section~\ref{secenclosed}.

\subsection{Boundary circuit}\label{secboundarycircuit}
In this section, we give an algorithm to construct a boundary circuit for any planar graph $g$ by adding 0-weight edges. The construction is such that all the vertices of the boundary $\partial g$ of $g$ are in the boundary circuit. The boundary MD partition function on the graph with the boundary circuit is, therefore, equal to that on $g$, and the Pfaffian associated to the graph with the boundary circuit is equal to that associated to $g$.
\bigskip

\indent First of all, if $g$ is disconnected, then we add 0-weight edges to it to connect its connected components to each other.

\indent Then, consider a closed path shadowing the boundary of $g$ from the outside, and denote by $(v_1,\cdots,v_n)$ the string (possibly with repetitions)
listing the vertices of the boundary in the order encountered along the path. We identify $v_{n+1}\equiv v_1$. Then consider the ordered sub-set $(v_{i_1},\cdots,v_{i_k})$ of $(v_1,\cdots,v_n)$ obtained by 
erasing the repetitions. If a pair $\{v_{i_j},v_{i_{j+1}}\}$, $j=1,\ldots,k$, is not an edge of $g$, then we add a $0$-weight edge from $v_{i_j}$ to $v_{i_{j+1}}$. 
By construction, $(v_{i_1},\cdots,v_{i_k})$ is the boundary circuit of the resulting graph. See figure \ref{figboundaryexample} for an example. 

\bigskip

\begin{figure}
\hfil\includegraphics[width=6cm]{Figs/boundary_circuit_naked.pdf}
\hfil\includegraphics[width=6cm]{Figs/boundary_circuit.pdf}\par\penalty10000
\medskip
\caption{A graph with no boundary circuit. In the leftmost figure, the edges and vertices of the boundary graph are drawn thicker and {\color{blue}blue}, and the dotted line represents the path shadowing the boundary from the outside, which we think of as starting and ending at $1$.  The corresponding string with repetitions is $(1,2,3,4,5,4,6,4,7,4,3,8,9,10,11,12,3,2,13)$.  After having erased the repetitions, we obtain the new string $(1,2,3,4,5,6,7,8,9,10,11,12,13)$. All the adjacent pairs but $\{5,6\}$, $\{6,7\}$, $\{7,8\}$ and $\{12,13\}$ are edges of $g$. In the rightmost figure, these four extra edges are added to the graph and drawn thicker and {\color{red}red}.}
\label{figboundaryexample}
\end{figure}

\indent Once the boundary circuit has been constructed, if the boundary circuit contains an even number of vertices, then the resulting graph is an enclosed graph and can be directed and labeled as in section~\ref{secenclosed}. If the boundary circuit contains an odd number of vertices then the graph can be further reduced to an enclosed graph as explained in the following section.

\subsection{Making a boundary circuit even}\label{secevenboundarycircuit}
In this section, we show how to add edges and vertices to a graph with a boundary circuit that contains an odd number of vertices to an enclosed graph, in such a way that the boundary MD partition function is unchanged. The procedure is simple: pick an edge of the boundary circuit, and 
replace the edge according to figure~\ref{figreplodd}.

\bigskip

\begin{figure}
\hfil\parbox[m]{4cm}{\includegraphics[width=4cm]{Figs/oddrepl_bef}}
\hfil$\longmapsto$
\hfil\parbox[m]{4cm}{\includegraphics[width=4cm]{Figs/oddrepl_aft}}\par\penalty10000
\medskip
\caption{Replacing an edge of the boundary circuit in order to make it contain an even number of edges. The weight of the thick {\color{blue}blue} (color online) edge is set to 1. Note that since the {\color{blue} blue} edge must be occupied in every boundary MD covering, the weights of the other two extra edges and the weight of the extra vertex on the boundary circuit do not affect the boundary MD partition function.}
\label{figreplodd}\end{figure}

\indent It is easy to check that, if the extra edge is given weight 1,  then the resulting graph has the same boundary MD partition function. In addition, the resulting graph is an enclosed graph, and can be directed and labeled as in section~\ref{secenclosed}, and it is straightforward to check that the Pfaffian computed from the graph with the extra edges and vertices is equal to that without. This concludes the proof of theorem~\ref{theomain}.
\vskip100pt

\hfil{\Large\bf Acknowledgments}\par
\bigskip
We thank Michael Aizenman and Hugo Duminil-Copin for discussing their work in progress on the random current representation for planar lattice models with us. We gratefully acknowledge financial support from the A*MIDEX project ANR-11-IDEX-0001-02 (A.G.), 
from the PRIN National Grant {\it Geometric and analytic theory of Hamiltonian systems in finite and infinite dimensions} (A.G. and I.J.), and 
NSF grant PHY-1265118 (E.H.L.). 
We also would like to thank Tom Spencer and Joel Lebowitz for their hospitality at the IAS in Princeton and their continued interest in this problem. 
\vfill
\eject

\appendix
\section{Examples}\label{app.A}
In this appendix we provide some examples of Pfaffian formulas to illustrate the discussion.

\subsection{A simple graph}
In this section, we compute the Pfaffian corresponding to the first graph of figure~\ref{figsimpleexample}, directed and labeled as in figure~\ref{figsimpleexamplelabels}. We set the edge weights $d_e=1$ and assume the monomer weights $\ell_i$ are all equal to $\sqrt{x}$. The antisymmetric matrix $A(\bm\ell,\mathbf d)$ is
$$
A(x)=\left(\begin{array}{cccccccc}
0&1+x&-x&x&-x&x&-x&1+x\\
&0&1+x&-x&x&-x&1+x&-x\\
&&0&1+x&1-x&x&1-x&x\\
&&&0&1+x&-x&x&-x\\
&&&&0&1+x&-x&x\\
&&&&&0&1+x&-x\\
&&&&&&0&1+x\\
&&&&&&&0
\end{array}\right)
$$
which is completed by antisymmetry. The MD partition function is therefore
\begin{equation}
\Xi(x)=\mathrm{pf}(A(x))=
x^4+11\,x^3+33\,x^2+28\,x+3.
\label{eqsimpleexample}\end{equation}

\subsection{Another simple graph: the L-shape}
In this section we compute the MD partition function for another simple graph: the {\it L-shape}, represented in figure~\ref{figLshape}. We direct and label the graph as per the discussion in section~\ref{secsimple} (see figure~\ref{figLshape}) and find (setting $d_v=1$ and $\ell_i=\sqrt{x}$ as before)
$$
A(x)=\left(\begin{array}{cccccccc}
0&1+x&-x&x&-x&x&-x&1+x\\
&0&1+x&-x&1+x&-x&x&-x\\
&&0&1+x&-x&x&-x&x\\
&&&0&1+x&-x&x&-x\\
&&&&0&1+x&-x&1+x\\
&&&&&0&1+x&-x\\
&&&&&&0&1+x\\
&&&&&&&0
\end{array}\right)
$$
which is completed by antisymmetry. The MD partition function is therefore
\begin{equation}
\Xi(x)=\mathrm{pf}(A(x))=
x^4+10\,x^3+28\,x^2+24\,x+4
\label{eqLshape}\end{equation}

\begin{figure}
\hfil\includegraphics{Figs/Lshape.pdf}
\hfil\includegraphics{Figs/Lshape_label.pdf}\par\penalty10000
\medskip
\captionshort{The L-shape graph.}
\label{figLshape}
\end{figure}

\subsection{An evenly filled graph}
In this section, we compute the Pfaffian corresponding to the graph in figure~\ref{figevenexample}, directed and labeled as in figure~\ref{figevenexamplelabels}. We set $d_e=1$ and $\ell_i=\sqrt{x}$. Since the expression of the matrix $A$ is rather long, we split it into lines and only write the $i<j$ terms.
$$\begin{array}{r@{\ }r}
A_{ 1,\cdot}(x)=& 1+x,  -x,   x,  -x,   x,  -x,   x,  -x,   x,  -x, 1+x,   0,   0,   0,   0\\
A_{ 2,\cdot}(x)=& 1+x,  -x,   x,  -x,   x,  -x,   x,  -x,   x,  -x, 1  ,   0,   0,   0\\
A_{ 3,\cdot}(x)=& 1+x,  -x,   x,  -x,   x,  -x,   x,  -x,   x,   0,   0, 1  ,   0\\
A_{ 4,\cdot}(x)=& 1+x,  -x,   x,  -x,   x,  -x,   x,  -x,   0,   0,   0,   0\\
A_{ 5,\cdot}(x)=& 1+x,  -x,   x,  -x,   x,  -x,   x,   0,   0, 1  ,   0\\
A_{ 6,\cdot}(x)=& 1+x,  -x,   x,  -x,   x,  -x,   0,   0,   0,-1  \\
A_{ 7,\cdot}(x)=& 1+x,  -x,   x,  -x,   x,   0,   0,   0,   0\\
A_{ 8,\cdot}(x)=& 1+x,  -x,   x,  -x,   0,   0,   0,-1  \\
A_{ 9,\cdot}(x)=& 1+x,  -x,   x,   0,-1  ,   0,   0\\
A_{10,\cdot}(x)=& 1+x,  -x,   0,   0,   0,   0\\
A_{11,\cdot}(x)=& 1+x,   0,-1  ,   0,   0\\
A_{12,\cdot}(x)=&-1  ,   0,   0,   0\\
A_{13,\cdot}(x)=& 1  ,-1  ,   0\\
A_{14,\cdot}(x)=&   0, 1  \\
A_{15,\cdot}(x)=& 1  .
\end{array}$$
The MD partition function is therefore
\begin{equation}
\Xi(x)=\mathrm{pf}(A(x))=
2x^6 + 40x^5 + 256x^4 + 680x^3 + 776x^2 + 336x + 36.
\label{eqevenexample}\end{equation}

\subsection{An enclosed graph}
In this section, we compute the Pfaffian corresponding to the graph in figure~\ref{figenclosedexample}, directed and labeled as in figure~\ref{figenclosedexamplecover}. We set $d_e=1$ and $\ell_i=\sqrt{x}$. Since the expression of the matrix $A$ is rather long, we split it into lines and only write the $i<j$ terms.
$$\begin{array}{r@{\ }r}
A_{ 1,\cdot}(x)=& 1+x,  -x,   x,  -x,   x,  -x, 1+x,   0,   0,   0,   0, 1  ,   0,   0,-1  \\
A_{ 2,\cdot}(x)=& 1+x,  -x,   x,  -x,   x,  -x,   0,   0,   0,   0,   0,   0,   0,   0\\
A_{ 3,\cdot}(x)=& 1+x,  -x,   x,  -x,   x,   0,   0,   0,   0,   0,   0,-1  ,   0\\
A_{ 4,\cdot}(x)=& 1+x, 1-x,   x,-1-x,   0, 1  ,   0, 1  ,   0,-1  ,   0,   0\\
A_{ 5,\cdot}(x)=& 1+x,  -x,   x,   0,   0,   0,   0,   0,   0,   0,   0\\
A_{ 6,\cdot}(x)=& 1+x,  -x, 1  ,   0,   0,   0,   0,   0,   0,   0\\
A_{ 7,\cdot}(x)=& 1+x, 1  ,   0,-1  ,   0,   0,   0,   0,   0\\
A_{ 8,\cdot}(x)=&   0,-1  ,-1  ,   0,-1  ,   0,   0,   0\\
A_{ 9,\cdot}(x)=&   0, 1  , 1  ,   0,   0,   0,   0\\
A_{10,\cdot}(x)=&   0,   0,   0,   0,   0,   0\\
A_{11,\cdot}(x)=& 1  ,   0,   0,   0,   0\\
A_{12,\cdot}(x)=&   0,   0,   0,   0\\
A_{13,\cdot}(x)=& 1  ,   0,   0\\
A_{14,\cdot}(x)=& 1  ,-1  \\
A_{15,\cdot}(x)=&   0.
\end{array}$$
The MD partition function is therefore
\begin{equation}
\Xi(x)=\mathrm{pf}(A(x))=
22x^2 + 40x + 4.
\label{eqenclosedexample}\end{equation}

\subsection{A graph with no boundary circuit}
In this section, we compute the Pfaffian corresponding to the graph in figure~\ref{figboundaryexample}, directed and labeled as in figure~\ref{figboundaryexampledir}. We set $d_e=1$ and $\ell_i=\sqrt{x}$. Since the expression of the matrix $A$ is rather long, we split it into lines and only write the $i<j$ terms.
$$\begin{array}{r@{\ }r}
A_{ 1,\cdot}(x)=& 1+x,  -x,   x,  -x,   x,  -x,   x,  -x,   x,  -x,   x,-1-x, 1  ,   0,   0\\
A_{ 2,\cdot}(x)=& 1+x,  -x,   x,  -x,   x,  -x,   x,  -x,   x,  -x, 1+x, 1  ,   0,   0\\
A_{ 3,\cdot}(x)=& 1+x,  -x,   x,  -x, 1+x,  -x,   x, 1-x, 1+x,  -x,   0, 1  ,   0\\
A_{ 4,\cdot}(x)=& 1+x, 1-x, 1+x,  -x,   x,  -x,   x,  -x,   x,   0,   0,   0\\
A_{ 5,\cdot}(x)=&   x,  -x,   x,  -x,   x,  -x,   x,  -x,   0,   0,   0\\
A_{ 6,\cdot}(x)=&   x,  -x,   x,  -x,   x,  -x,   x,   0,   0,   0\\
A_{ 7,\cdot}(x)=&   x,  -x,   x,  -x,   x,  -x,   0,   0,   0\\
A_{ 8,\cdot}(x)=& 1+x,  -x,   x,  -x,   x,   0,   0,   0\\
A_{ 9,\cdot}(x)=& 1+x,  -x,   x,  -x,   0, 1  ,   0\\
A_{10,\cdot}(x)=& 1+x,  -x,   x,   0, 1  ,   0\\
A_{11,\cdot}(x)=& 1+x,  -x,   0,   0,-1  \\
A_{12,\cdot}(x)=&   x,   0,   0,   0\\
A_{13,\cdot}(x)=& 1  ,   0,   0\\
A_{14,\cdot}(x)=&   0,   0\\
A_{15,\cdot}(x)=& 1 .
\end{array}$$
The MD partition function is therefore
\begin{equation}
\Xi(x)=\mathrm{pf}(A(x))=
3x^6 + 47x^5 + 222x^4 + 389x^3 + 234x^2 + 27x
\label{eqboundaryexample}\end{equation}

\begin{figure}
\hfil\includegraphics[width=6cm]{Figs/boundary_circuit_label.pdf}\par\penalty10000
\medskip
\captionshort{Directing and labeling the graph in figure~\ref{figboundaryexample}.}
\label{figboundaryexampledir}
\end{figure}

\section{An algorithm for the full monomer-dimer partition function}
\label{appalg}

\indent In this appendix, we discuss an algorithm to compute the {\it full} MD partition function on an arbitrary planar graph.

\indent The main idea is to isolate a {\it skeleton} $s$ from the graph, which is a sub-graph of $g$ obtained by removing edges from $g$ in such a way that $s$ contains no internal vertices. The boundary MD partition function of $s$ is the partition function of MD coverings of $g$ that does not have any dimers outside the skeleton. In order to count the coverings that do have dimers outside the skeleton, we add the following terms to the partition function. For every collection $\sigma$ of dimers that occupy edges that are outside the skeleton, we construct a sub-graph $[s]_\sigma$ of $s$ by removing the vertices covered by a dimer in $\sigma$. The boundary MD partition function of this sub-graph can be computed using theorem~\ref{theomain}. The full MD partition function is then obtained by summing the boundary MD partition functions of every such $[s]_\sigma$.

\bigskip

\indent If $g$ is an $L\times M$ sub-rectangle of $\mathbb Z^2$ with, say, $L$ even, then the skeleton can be constructed as in figure~(\ref{figskeleton}). By this algorithm, the MD partition function can be computed by summing $2^{\frac12(L-2)(M-2)}$ Pfaffians.
\bigskip

\begin{figure}
\hfil\includegraphics[width=5cm]{Figs/comb.pdf}\par\penalty10000
\medskip
\captionshort{A $10\times 7$ rectangle and its skeleton, colored grey.}
\label{figskeleton}
\end{figure}

\indent For example, if $L=4$, $M=3$ then, aside from the skeleton, there is a single sub-graph to be considered, see figure~\ref{figalgexample1}. The MD partition function is therefore the sum of two Pfaffians, which we have computed in the case $d_e=1$, $\ell_v=\sqrt{x}$:
\begin{equation}
\Xi(x)=
x^6 + 17x^5 + 102x^4 + 267x^3 + 302x^2 + 123x + 11.
\label{eqpfaff3x2}\end{equation}
If $L=6$, $M=6$, then the MD partition function is obtained by summing 256 Pfaffians:
\begin{equation}\begin{array}{r@{\ }l} 
\Xi(x)=&x^{18}+60 x^{17} + 1\,622\, x^{16} + 26\,172\, x^{15} + 281\,514 x^{14} +2\,135\,356\, x^{13}\\
&+ 11\,785\,382\, x^{12} + 
48\,145\,820\, x^{11} + 146\,702\,793\, x^{10} +
 333\,518\,324\, x^9\\
&+    562\,203\,148\, x^8 + 693\,650\,988\, x^7 + 613\,605\,045\, x^6 + 377\,446\,076\, x^5\\
&+ 154\,396\,898\, x^4 + 39\,277\,112\, x^3 +  5\,580\,152\, x^2 + 363\,536\, x +
 6\,728\;.
\end{array}\label{eqpfaff5x5}\end{equation}
Both~(\ref{eqpfaff3x2}) and~(\ref{eqpfaff5x5}) are in agreement with the results published in [\cite{Kr06}, Table~6.7, column $N=12$] and [\cite{Kr06}, Table~6.3] respectively.
\hugeskip

\begin{figure}
\hfil\includegraphics[width=3cm]{Figs/3x2_skel.pdf}
\hfil\includegraphics[width=3cm]{Figs/3x2_subskel.pdf}\par\penalty10000
\medskip
\captionshort{The skeleton and its only sub-graph for the $3\times2$ rectangle.}
\label{figalgexample1}
\end{figure}

\vfill
\eject

\references
\small
\BBlography



\end{document}