diff options
| -rw-r--r-- | Figs/bethe.pdf | bin | 3573 -> 0 bytes | |||
| -rw-r--r-- | Figs/enclosed_example.pdf | bin | 2068 -> 2046 bytes | |||
| -rw-r--r-- | Figs/enclosed_example_auxiliary.pdf (renamed from Figs/even_example_cover.pdf) | bin | 12786 -> 14564 bytes | |||
| -rw-r--r-- | Figs/enclosed_example_auxiliary_cover.pdf | bin | 21791 -> 14623 bytes | |||
| -rw-r--r-- | Figs/enclosed_example_cover.pdf | bin | 21279 -> 13374 bytes | |||
| -rw-r--r-- | Figs/enclosed_example_directed.pdf | bin | 11956 -> 11935 bytes | |||
| -rw-r--r-- | Figs/enclosed_example_monomer_auxiliary_cover.pdf | bin | 21272 -> 0 bytes | |||
| -rw-r--r-- | Figs/enclosed_example_monomer_cover.pdf | bin | 20765 -> 0 bytes | |||
| -rw-r--r-- | Figs/etareplace_cross.pdf | bin | 1139 -> 0 bytes | |||
| -rw-r--r-- | Figs/etareplace_empty.pdf | bin | 1329 -> 0 bytes | |||
| -rw-r--r-- | Figs/etareplace_occupied.pdf | bin | 1330 -> 0 bytes | |||
| -rw-r--r-- | Figs/etareplace_r.pdf | bin | 1322 -> 0 bytes | |||
| -rw-r--r-- | Figs/even_example_auxcover.pdf | bin | 12487 -> 0 bytes | |||
| -rw-r--r-- | Figs/even_example_auxiliary.pdf | bin | 12442 -> 0 bytes | |||
| -rw-r--r-- | Figs/even_example_label_pre.pdf | bin | 12444 -> 0 bytes | |||
| -rw-r--r-- | Figs/even_example_monomer.pdf | bin | 12323 -> 0 bytes | |||
| -rw-r--r-- | Figs/extended_dimer.pdf | bin | 19552 -> 0 bytes | |||
| -rw-r--r-- | Figs/extended_dimer_triangle.pdf | bin | 22197 -> 0 bytes | |||
| -rw-r--r-- | Figs/noncoverable.pdf | bin | 1730 -> 0 bytes | |||
| -rw-r--r-- | Figs/simple_example_auxiliary.pdf | bin | 11040 -> 0 bytes | |||
| -rw-r--r-- | Figs/simple_example_monomers.pdf | bin | 10964 -> 0 bytes | |||
| -rw-r--r-- | Figs/square.pdf | bin | 0 -> 1265 bytes | |||
| -rw-r--r-- | Figs/square_auxiliary.pdf | bin | 0 -> 11722 bytes | |||
| -rw-r--r-- | Figs/triangle_3.pdf | bin | 1309 -> 0 bytes | |||
| -rw-r--r-- | Figs/triangle_3_Xcover1.pdf | bin | 1140 -> 0 bytes | |||
| -rw-r--r-- | Figs/triangle_3_Xcover3.pdf | bin | 1140 -> 0 bytes | |||
| -rw-r--r-- | Figs/triangle_3_cover1.pdf | bin | 1327 -> 0 bytes | |||
| -rw-r--r-- | Figs/triangle_3_cover3.pdf | bin | 1332 -> 0 bytes | |||
| -rw-r--r-- | Figs/triangle_3_pre.pdf | bin | 1133 -> 0 bytes | |||
| -rw-r--r-- | Figs/triangle_4.pdf | bin | 1442 -> 0 bytes | |||
| -rw-r--r-- | Figs/triangle_4_pre.pdf | bin | 1124 -> 0 bytes | |||
| -rw-r--r-- | Figs/triangle_5.pdf | bin | 1608 -> 0 bytes | |||
| -rw-r--r-- | Figs/triangle_5_directed.pdf | bin | 10716 -> 0 bytes | |||
| -rw-r--r-- | Figs/triangle_5_pre.pdf | bin | 1145 -> 0 bytes | |||
| -rw-r--r-- | Figs/triangle_groups_l.pdf | bin | 32303 -> 0 bytes | |||
| -rw-r--r-- | Figs/triangle_groups_lr.pdf | bin | 33548 -> 0 bytes | |||
| -rw-r--r-- | Figs/triangle_groups_r.pdf | bin | 10718 -> 0 bytes | |||
| -rw-r--r-- | Giuliani_Jauslin_Lieb_2015.tex | 1109 | ||||
| -rw-r--r-- | bibliography.BBlog.tex | 1 | ||||
| -rw-r--r-- | iansecs.sty | 10 | ||||
| -rw-r--r-- | toolbox.sty | 13 |
41 files changed, 279 insertions, 854 deletions
diff --git a/Figs/bethe.pdf b/Figs/bethe.pdf Binary files differdeleted file mode 100644 index 7a02d88..0000000 --- a/Figs/bethe.pdf +++ /dev/null diff --git a/Figs/enclosed_example.pdf b/Figs/enclosed_example.pdf Binary files differindex 2df6492..2a75890 100644 --- a/Figs/enclosed_example.pdf +++ b/Figs/enclosed_example.pdf diff --git a/Figs/even_example_cover.pdf b/Figs/enclosed_example_auxiliary.pdf Binary files differindex 2985cd9..24286d4 100644 --- a/Figs/even_example_cover.pdf +++ b/Figs/enclosed_example_auxiliary.pdf diff --git a/Figs/enclosed_example_auxiliary_cover.pdf b/Figs/enclosed_example_auxiliary_cover.pdf Binary files differindex edfd9d8..78fea38 100644 --- a/Figs/enclosed_example_auxiliary_cover.pdf +++ b/Figs/enclosed_example_auxiliary_cover.pdf diff --git a/Figs/enclosed_example_cover.pdf b/Figs/enclosed_example_cover.pdf Binary files differindex a26c5a6..8d7406c 100644 --- a/Figs/enclosed_example_cover.pdf +++ b/Figs/enclosed_example_cover.pdf diff --git a/Figs/enclosed_example_directed.pdf b/Figs/enclosed_example_directed.pdf Binary files differindex 4244482..b5089bb 100644 --- a/Figs/enclosed_example_directed.pdf +++ b/Figs/enclosed_example_directed.pdf diff --git a/Figs/enclosed_example_monomer_auxiliary_cover.pdf b/Figs/enclosed_example_monomer_auxiliary_cover.pdf Binary files differdeleted file mode 100644 index 19a91cf..0000000 --- a/Figs/enclosed_example_monomer_auxiliary_cover.pdf +++ /dev/null diff --git a/Figs/enclosed_example_monomer_cover.pdf b/Figs/enclosed_example_monomer_cover.pdf Binary files differdeleted file mode 100644 index 80e6f38..0000000 --- a/Figs/enclosed_example_monomer_cover.pdf +++ /dev/null diff --git a/Figs/etareplace_cross.pdf b/Figs/etareplace_cross.pdf Binary files differdeleted file mode 100644 index fa9d840..0000000 --- a/Figs/etareplace_cross.pdf +++ /dev/null diff --git a/Figs/etareplace_empty.pdf b/Figs/etareplace_empty.pdf Binary files differdeleted file mode 100644 index 48f6deb..0000000 --- a/Figs/etareplace_empty.pdf +++ /dev/null diff --git a/Figs/etareplace_occupied.pdf b/Figs/etareplace_occupied.pdf Binary files differdeleted file mode 100644 index ef11b35..0000000 --- a/Figs/etareplace_occupied.pdf +++ /dev/null diff --git a/Figs/etareplace_r.pdf b/Figs/etareplace_r.pdf Binary files differdeleted file mode 100644 index 70d7dba..0000000 --- a/Figs/etareplace_r.pdf +++ /dev/null diff --git a/Figs/even_example_auxcover.pdf b/Figs/even_example_auxcover.pdf Binary files differdeleted file mode 100644 index e7a7e37..0000000 --- a/Figs/even_example_auxcover.pdf +++ /dev/null diff --git a/Figs/even_example_auxiliary.pdf b/Figs/even_example_auxiliary.pdf Binary files differdeleted file mode 100644 index cce5f35..0000000 --- a/Figs/even_example_auxiliary.pdf +++ /dev/null diff --git a/Figs/even_example_label_pre.pdf b/Figs/even_example_label_pre.pdf Binary files differdeleted file mode 100644 index 5ba8b2c..0000000 --- a/Figs/even_example_label_pre.pdf +++ /dev/null diff --git a/Figs/even_example_monomer.pdf b/Figs/even_example_monomer.pdf Binary files differdeleted file mode 100644 index cae96f9..0000000 --- a/Figs/even_example_monomer.pdf +++ /dev/null diff --git a/Figs/extended_dimer.pdf b/Figs/extended_dimer.pdf Binary files differdeleted file mode 100644 index 8fc0b67..0000000 --- a/Figs/extended_dimer.pdf +++ /dev/null diff --git a/Figs/extended_dimer_triangle.pdf b/Figs/extended_dimer_triangle.pdf Binary files differdeleted file mode 100644 index efc0885..0000000 --- a/Figs/extended_dimer_triangle.pdf +++ /dev/null diff --git a/Figs/noncoverable.pdf b/Figs/noncoverable.pdf Binary files differdeleted file mode 100644 index 754d434..0000000 --- a/Figs/noncoverable.pdf +++ /dev/null diff --git a/Figs/simple_example_auxiliary.pdf b/Figs/simple_example_auxiliary.pdf Binary files differdeleted file mode 100644 index 9282f37..0000000 --- a/Figs/simple_example_auxiliary.pdf +++ /dev/null diff --git a/Figs/simple_example_monomers.pdf b/Figs/simple_example_monomers.pdf Binary files differdeleted file mode 100644 index 74738db..0000000 --- a/Figs/simple_example_monomers.pdf +++ /dev/null diff --git a/Figs/square.pdf b/Figs/square.pdf Binary files differnew file mode 100644 index 0000000..39737d9 --- /dev/null +++ b/Figs/square.pdf diff --git a/Figs/square_auxiliary.pdf b/Figs/square_auxiliary.pdf Binary files differnew file mode 100644 index 0000000..f5471c8 --- /dev/null +++ b/Figs/square_auxiliary.pdf diff --git a/Figs/triangle_3.pdf b/Figs/triangle_3.pdf Binary files differdeleted file mode 100644 index 696649c..0000000 --- a/Figs/triangle_3.pdf +++ /dev/null diff --git a/Figs/triangle_3_Xcover1.pdf b/Figs/triangle_3_Xcover1.pdf Binary files differdeleted file mode 100644 index 7516045..0000000 --- a/Figs/triangle_3_Xcover1.pdf +++ /dev/null diff --git a/Figs/triangle_3_Xcover3.pdf b/Figs/triangle_3_Xcover3.pdf Binary files differdeleted file mode 100644 index 8f07a93..0000000 --- a/Figs/triangle_3_Xcover3.pdf +++ /dev/null diff --git a/Figs/triangle_3_cover1.pdf b/Figs/triangle_3_cover1.pdf Binary files differdeleted file mode 100644 index c200454..0000000 --- a/Figs/triangle_3_cover1.pdf +++ /dev/null diff --git a/Figs/triangle_3_cover3.pdf b/Figs/triangle_3_cover3.pdf Binary files differdeleted file mode 100644 index 05bcc4c..0000000 --- a/Figs/triangle_3_cover3.pdf +++ /dev/null diff --git a/Figs/triangle_3_pre.pdf b/Figs/triangle_3_pre.pdf Binary files differdeleted file mode 100644 index fe121fd..0000000 --- a/Figs/triangle_3_pre.pdf +++ /dev/null diff --git a/Figs/triangle_4.pdf b/Figs/triangle_4.pdf Binary files differdeleted file mode 100644 index d779fa3..0000000 --- a/Figs/triangle_4.pdf +++ /dev/null diff --git a/Figs/triangle_4_pre.pdf b/Figs/triangle_4_pre.pdf Binary files differdeleted file mode 100644 index c38fd0c..0000000 --- a/Figs/triangle_4_pre.pdf +++ /dev/null diff --git a/Figs/triangle_5.pdf b/Figs/triangle_5.pdf Binary files differdeleted file mode 100644 index 3f0bc4e..0000000 --- a/Figs/triangle_5.pdf +++ /dev/null diff --git a/Figs/triangle_5_directed.pdf b/Figs/triangle_5_directed.pdf Binary files differdeleted file mode 100644 index f98fb40..0000000 --- a/Figs/triangle_5_directed.pdf +++ /dev/null diff --git a/Figs/triangle_5_pre.pdf b/Figs/triangle_5_pre.pdf Binary files differdeleted file mode 100644 index 3a911ff..0000000 --- a/Figs/triangle_5_pre.pdf +++ /dev/null diff --git a/Figs/triangle_groups_l.pdf b/Figs/triangle_groups_l.pdf Binary files differdeleted file mode 100644 index 86aa908..0000000 --- a/Figs/triangle_groups_l.pdf +++ /dev/null diff --git a/Figs/triangle_groups_lr.pdf b/Figs/triangle_groups_lr.pdf Binary files differdeleted file mode 100644 index cbe3ddf..0000000 --- a/Figs/triangle_groups_lr.pdf +++ /dev/null diff --git a/Figs/triangle_groups_r.pdf b/Figs/triangle_groups_r.pdf Binary files differdeleted file mode 100644 index 772012c..0000000 --- a/Figs/triangle_groups_r.pdf +++ /dev/null diff --git a/Giuliani_Jauslin_Lieb_2015.tex b/Giuliani_Jauslin_Lieb_2015.tex index a52767c..e539376 100644 --- a/Giuliani_Jauslin_Lieb_2015.tex +++ b/Giuliani_Jauslin_Lieb_2015.tex @@ -51,18 +51,23 @@ Clearly, $\Xi(z)$ is a polynomial in $z$, and $z$ is called the {\it monomer fug ``$\# 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 derive a Pfaffian formula, based on the ``Temperley bijection'' [\cite{Te74}], for the partition function of a system with a {\it single} monomer located on the boundary of a finite square lattice, and in [\cite{WTI11}], on a cylinder of odd width (which is a nonbipartite 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 the product of two Pfaffians. +\bigskip + +\indent In the present work, we prove a Pfaffian formula for the {\it boundary} MD partition function on an {\it arbitrary} planar graph (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. + +\indent It was later brought to our attention by an anonymous referee that it is known that the boundary MD partition function can be given by {\it a} Pfaffian formula, which one can obtain by considering a bijection between the boundary MD coverings of a graph and the pure dimer coverings of a larger graph, whose partition function is known, by Kasteleyn's theorem~\cite{Ka63}, to be expressible as a Pfaffian. This construction is detailed in appendix~\ref{appbijectionmethod}. To our knowledge, this result has, so far, not been published, even though it appears to be closely related to the discussion in [\cite{Ku94}, section 4]. -\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 at 0-monomer density (see~(\ref{eqcorrdef}) for a precise definition). -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. +\indent Oblivious to the existence of this bijection method, the approach we have adopted in this paper is a different one. Instead of mapping the boundary MD coverings to pure dimer coverings of a larger graph, we compute, for each fixed monomer positions, the pure dimer partition function on the subgraph obtained by removing the vertices covered by monomers, which, by Kasteleyn's theorem, is expressible as a Pfaffian, and combine all the Pfaffians thus obtained into a single Pfaffian using a theorem proved by one of the authors in 1968~[\cite{Li68}]. The formula we obtained in this way is slightly different from that obtained by the bijection method, and we have found that, by using this formula, the monomer correlations functions at close packing can easily be shown to satisfy a fermionic Wick rule. + +\indent In short, the aim of this paper is, first, to leave a written trace of the fact that the boundary MD partition function can be expressed as a Pfaffian, and, second, to present a Pfaffian formula, which is not a trivial rewriting of the formula one obtains by the bijection method, and may be easier to use than the latter formula in some cases, for instance in the proof of the Wick rule. + +\indent Finally, it should be mentioned that, by drawing inspiration from the bijection method detailed by our anonymous referee, we found a significant simplification of our proof, and we are, therefore, very grateful. \bigskip {\bf Remarks}: \listparpenalty \begin{itemize} -\item The asymptotic behavior of monomer pair correlations on the square lattice have been computed explicitly [\cite{FS63}, \cite{Ha66}, \cite{FH69}] for monomers on a row, column or diagonal (note that, as mentionned in~[\cite{AP84}], [\cite{Ha66}] contains small mistakes). In addition, the general bulk monomer pair correlations have been shown~[\cite{AP84}] to be expressible in terms of two critical Ising correlation functions. +\item The asymptotic behavior of monomer pair correlations on the square lattice have been computed explicitly [\cite{FS63}, \cite{Ha66}, \cite{FH69}] for monomers on a row, column or diagonal (note that, as mentioned in~[\cite{AP84}], [\cite{Ha66}] contains small mistakes). In addition, the general bulk monomer pair correlations have been shown~[\cite{AP84}] to be expressible in terms of two critical Ising correlation functions. \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. @@ -126,6 +131,7 @@ a_{i,j}(\mathbf d):=\left\{ \right. \label{eqAdef}\end{equation} and, for $i<j$, +\nopagebreakaftereq \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} @@ -134,6 +140,7 @@ and $A_{j,i}(\bm\ell,\mathbf d):=-A_{i,j}(\bm\ell,\mathbf d)$, the boundary MD p \Xi_\partial(\bm\ell,\mathbf d)=\mathrm{pf}(A(\bm\ell,\mathbf d)). \label{eqtheo}\end{equation} \endtheo +\restorepagebreakaftereq \bigskip {\bf Remarks}: @@ -178,54 +185,24 @@ where $\mathfrak M_{i_1,\ldots,i_{2n}}$ is the $2n\times 2n$ antisymmetric matri \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. +\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 an auxiliary graph in which the boundary MD coverings of $g$ are mapped to dimer coverings by a map that preserves positivity. We can then show that the auxiliary graph is positive, which implies the positivity of the sub-graphs of $g$. \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. +\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{secenclosed}, we prove theorem~\ref{theomain} for a class of graphs called {\it enclosed graphs}. +\item In section~\ref{secreduce}, 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 an enclosed graph. +\item In appendix~\ref{apppropkasteleyn}, we state some useful properties of Kasteleyn graphs, and prove some of the statements of section~\ref{secpreliminaries}. +\item In appendix~\ref{appexamples}, we give several examples of the Pfaffian formula. +\item In appendices~\ref{appalg} and~\ref{appinout} we present two algorithms to compute the {\it full} monomer-dimer partition function on arbitrary planar graphs. +\item In appendix~\ref{appbijectionmethod}, we discuss the bijection method. \end{itemize} -\enddelim -\unlistparpenalty - \section{Preliminaries}\label{secpreliminaries} \indent 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}. +Pfaffian formula for the boundary MD partition function. \bigskip \subsection{Kasteleyn's theorem}\label{subseckasteleyn} @@ -303,7 +280,7 @@ 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}. +\indent The adjective ``minimal'' can be dropped from definition~\ref{defkasteleyn}, as shown in the following lemma, which we will prove in appendix~\ref{apppropkasteleyn}. \bigskip \theo{Lemma}\label{lemmakasteleyncomplete} @@ -329,7 +306,7 @@ 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}. +For a proof and an algorithmic construction, see appendix \ref{apppropkasteleyn}. \bigskip \point{\bf The positivity condition.} @@ -389,10 +366,12 @@ constructively, which in turn implies the following \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} +\nopagebreakaftereq +\begin{equation} +\Xi(0,\mathbf d)=\mathrm{pf}(a(\mathbf d)). +\label{eqkasteleyntheo}\end{equation} \endtheo +\restorepagebreakaftereq \medskip \indent Note that, as commented above, every planar graph can be directed and labeled so as to make it Kasteleyn and positive. @@ -524,10 +503,12 @@ M_n(i_1,\cdots,i_{2n})=& =&\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 +\nopagebreakaftereq \begin{equation} (-a^{-1}(\mathbf d))_{i,j}=M_1(i,j). \label{eqM1a}\end{equation} -\hfill$\square$ +\qed +\restorepagebreakaftereq \bigskip \makelink{rkWick}{remark}{\bf Remark}: We have shown that theorem~\ref{theomain} implies corollary~\ref{corrmain}. It turns out that the converse is also true assuming~(\ref{eqM1a}) holds (with the sign that appears in~(\ref{eqM1a})). More precisely, corollary~\ref{corrmain} and~(\ref{eqM1a}) imply theorem~\ref{theomain}. Indeed, (\ref{eqM1a}) and corollary~\ref{corrmain} imply @@ -537,164 +518,186 @@ $$ which, by~(\ref{eqkasteleyntheo}), (\ref{eqpfminors}) and theorem~\ref{theolieb}, yields~(\ref{eqtheo}). As a consequence, if one were to prove the Wick rule for boundary monomers (possibly by extending the analysis of~[\cite{GBK78}] to the monomer-dimer problem) then the Pfaffian formula~(\ref{eqtheo}) could be recovered by directing and labeling the graph $g$ in such a way that~(\ref{eqM1a}) holds, which can be achieved by ensuring that $[g]_{\{v,v'\}}$ is positive and Kasteleyn for every $v,v'\in\mathcal V(\partial g)$ (in the present paper, we prove the Pfaffian formula~(\ref{eqtheo}) without first proving the Wick rule, and ensuring that $[g]_{\mathcal I}$ is Kasteleyn and positive for every $\mathcal I\subset\mathcal V(\partial g)$, which does not seem to be harder than proving it for sets of cardinality 2). In other words, the Pfaffian formula~(\ref{eqtheo}) that counts MD coverings with any number of monomers on the boundary can be seen as a consequence of a similar Pfaffian formula for the MD coverings with 2 monomers on the boundary and the Wick rule. -\section{Simple graphs}\label{secsimple} +\section{Proof of the main result for enclosed graphs}\label{secenclosed} -\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$. +\indent We first consider a class of graphs, called the set of {\it enclosed graphs}, that have a boundary circuit, and will subsequently show how to reduce any graph to such a case. +\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$ (which may be empty) 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. \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 +\hfil\includegraphics[width=6cm]{Figs/enclosed_example.pdf}\par\penalty10000 +\medskip +\captionshort{An enclosed graph.} +\label{figenclosedexample}\end{figure} +\bigskip + +\indent In the following, we will need to generalize the notion of positivity of a dimer covering to boundary monomer-dimer coverings (hereafter abbreviated as ``bMD coverings''). A bMD covering of a graph $g$ is said to be \defd{positive} if and only if the corresponding dimer covering of the graph obtained by removing the vertices occupied by monomers is positive. \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. +\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 \begin{figure} -\hfil\includegraphics[width=5cm]{Figs/comb.pdf}\par\penalty10000 +\hfil\includegraphics[width=6cm]{Figs/enclosed_example_directed.pdf} +\hfil\includegraphics[width=6cm]{Figs/enclosed_example_cover.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} +\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 a bMD of $g$ with monomers at 2, 5, 7, 8, and an associated labeling. The labels are chosen in such a way that this covering is positive: +$(16,1)$, $(15,3)$, $(4,10)$, $(6,9)$, $(11,12)$, $(13,14)$.} +\label{figenclosedexamplecover}\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')$. +\delimtitle{\bf Directing and labeling an enclosed graph} +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 appendix~\ref{apppropkasteleyn}. + +\indent Finally, we label the remaining vertices in such a way that the resulting labeled graph is positive, by considering a random labeling, checking its sign, and exchanging two labels if it is negative, thus ensuring its positivity. The sign of the labeling can be computed either by constructing a dimer covering (or, more in general, a boundary monomer-dimer covering) and computing its sign, or by setting all weights $\ell_i=d_i=1$ and computing the sign of the right side of the Pfaffian formula~(\ref{eqtheo}). \enddelim \bigskip +\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 obtain~(\ref{eqtheo}). This result is contained in the following lemma, from which theorem~\ref{theomain}, restricted to the case of enclosed graphs, follows. +\bigskip + +\indent Given a family of monomers $\mathcal M\subsetneq\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$. +\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$ is Kasteleyn and positive. +\endtheo +\medskip + +\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 $\gamma$ which is Kasteleyn and positive, and exhibit a mapping $\lambda_\gamma$ from dimer coverings of $[g]_{\mathcal M}$ to dimer coverings of $\gamma$, which preserves the sign of the covering, from which we conclude that $[g]_{\mathcal M}$ is positive. +\medskip + +\indent We construct $\gamma$ from $g$ in the following way (see figure~\ref{figenclosedauxiliary} for an example). We add an extra circuit of vertices $\epsilon$ outside of $g$, which consists of $|\partial g|$ vertices. The edges and vertices of $\gamma$ that are also edges or vertices of $g$ are directed and labeled in the same way as in $g$. We then label the vertices of $\epsilon$ sequentially in the counterclockwise direction from $|g|+1$ to $|g|+|\partial g|$ (the location of the first vertex is unimportant) and denote the resulting labeling by $\omega_\gamma$. We direct the edges of $\epsilon$ in such a way that $v\succ v'$ if and only if $\omega_\gamma(v)<\omega_\gamma(v')$, and add the following directed edges: +\begin{itemize} +\item $(\omega_\gamma^{-1}(2j-1),\omega_\gamma^{-1}(|g|+2j-1))$ and $(\omega_\gamma^{-1}(2j-1),\omega_\gamma^{-1}(|g|+2j-2))$ for $2\le j\le|\partial g|/2$ +\item $(\omega_\gamma^{-1}(|g|+2j),\omega_\gamma^{-1}(2j))$ and $(\omega_\gamma^{-1}(|g|+2j-1),\omega_\gamma^{-1}(2j))$ for $1\le j\le|\partial g|/2$ +\item $(\omega_\gamma^{-1}(1),\omega_\gamma^{-1}(|g|+1))$ and $(\omega_\gamma^{-1}(|g|+|\partial g|),\omega_\gamma^{-1}(1))$. +\end{itemize} +One readily checks that $\gamma$, thus directed, is Kasteleyn. +\bigskip + \begin{figure} -\hfil\includegraphics[width=4cm]{Figs/simple_example_labels.pdf}\par\penalty10000 +\hfil\includegraphics[width=10cm]{Figs/enclosed_example_auxiliary.pdf}\par\penalty10000 \medskip -\captionshort{The labeling and direction for the first simple graph in -figure~\ref{figsimpleexample}.} -\label{figsimpleexamplelabels}\end{figure} +\caption{The auxiliary graph associated to the graph in figure~\ref{figenclosedexample}. The extra edges are rendered as thick {\color{blue}blue} (color online) lines.} +\label{figenclosedauxiliary}\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. +\indent We now construct an injective mapping $\lambda_{\gamma}$ from the set of bMD coverings of $g$ to the set of dimer coverings of $\gamma$. Given a bMD covering $\sigma$ of $g$, we construct $\lambda_\gamma(\sigma)$ in the following way (see figure~\ref{figenclosedauxiliarycover} for an example). We first add every dimer of $\sigma$ to $\lambda_\gamma(\sigma)$. For $1\le j\le|\partial g|$, let $p_j:=\mathrm{card}\{i< j\ |\ i\in\mathcal M\}$. For every $j\in\mathcal M$, +\begin{itemize} +\item if $j+p_j$ is odd, then we add $\{\omega_\gamma^{-1}(j),\omega_\gamma^{-1}(|g|+j)\}$ to $\lambda_\gamma(\sigma)$ +\item if $j+p_j$ is even, then we add $\{\omega_\gamma^{-1}(j),\omega_\gamma^{-1}(|g|+j-1)\}$ to $\lambda_\gamma(\sigma)$. +\end{itemize} +In addition, for every $j\in\{1,\cdots,|\partial g|\}\setminus\mathcal M$, +\begin{itemize} +\item if $j+p_j$ is even, then we add $\{\omega_\gamma^{-1}(|g|+j),\omega_\gamma^{-1}(|g|+j-1)\}$ to $\lambda_\gamma(\sigma)$. +\end{itemize} +One readily checks that none of the dimers added in this way overlap, and that no vertices are left uncovered (in order to carry out the proof of this fact, it is convenient to consider the procedure described above from an algorithmic point of view, that is, considering each $j\in\{1,\cdots,|\partial g|\}$ successively, checking whether $j\in\mathcal M$ or not and the parity of $j+p_j$, and adding a dimer following the rules above; it is then straightforward to prove the property by induction on $j$). \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 +\hfil\includegraphics[width=10cm]{Figs/enclosed_example_auxiliary_cover.pdf}\par\penalty10000 \medskip +\caption{The dimer covering associated to the bMD in figure~\ref{figenclosedexamplecover}.} +\label{figenclosedauxiliarycover}\end{figure} +\bigskip + +\indent We will now prove that $\lambda_\gamma$ preserves the sign of $\sigma$. To do so, we first note that the two following edges are not occupied by a dimer of $\lambda_\gamma(\sigma)$: +\begin{itemize} +\item $(\omega_\gamma^{-1}(|g|+|\partial g|),\omega_\gamma^{-1}(1))$ (since if $1\in\mathcal M$, then $\{\omega^{-1}_\gamma(1),\omega_\gamma^{-1}(|g|+1)\}$ is a dimer of $\lambda_\gamma(\sigma)$), +\item $(\omega_\gamma^{-1}(|g|+1),\omega_\gamma^{-1}(|g|+|\partial g|))$ (by construction). +\end{itemize} + This means that every every edge $\{v,v'\}$ with $v\in\mathcal V(\epsilon)$ and $v'\in\mathcal V(\partial g)$ that is occupied by a dimer of $\lambda_\gamma(\sigma)$ is directed as $v\succ v'$ if and only if $\omega_\gamma(v')$ is even, and that every edge $\{v,v'\}$ with $v,v'\in\mathcal V(\epsilon)$ that is occupied by a dimer and is directed $v\succ v'$ satisfies $\omega_\gamma(v')=\omega_\gamma(v)+1$. -\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 +\indent We write the dimer covering $\lambda_\gamma(\sigma)$ as a sequence of labels +$$(j_1,j_2,\cdots,j_{|g|+|\epsilon|-1},j_{|g|+|\epsilon|})$$ +in which \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}|)$. +\item $\{\omega_\gamma(j_{2i-1}),\omega_\gamma(j_{2i})\}$ is occupied by a dimer of $\lambda_\gamma(\sigma)$ and is oriented $\omega_\gamma(j_{2i-1})\succ\omega_\gamma(j_{2i})$, +\item $j_1,\cdots,j_{|g|-|\mathcal M|}\in\mathcal V(g)\setminus\mathcal M$ +\item $\min\{j_{2i-1},j_{2i}\}<\min\{j_{2i'-1},j_{2i'}\}$ if and only if $i<i'$. \end{itemize} -See figure~\ref{figsimpleexamplemonomers} for an example. +The sign of $\lambda_\gamma(\sigma)$ is the signature of the permutation that orders the indices $j_i$. We first focus on +$$(j_1,\cdots,j_{|g|-|\mathcal M|})$$ +that is, on the indices corresponding to dimers of $g$. This sequence can be ordered by a permutation of signature $s$ where $s$ is the sign of $\sigma$. We denote the resulting ordered sequence by +$$(j'_1,\cdots,j'_{|g|-|\mathcal M|}).$$ +We now focus on +$$(j_{|g|-|\mathcal M|+1},\cdots,j_{|g|+|\mathcal M|})$$ +that is, on the indices corresponding to dimers covering edges between $\epsilon$ and $\partial g$. We first reorder these $j$'s in such a way that $j_{2i-1}\in\{1,\cdots,|\partial g|\}$ and $j_{2i}>|g|$ by a permutation whose signature is $(-1)^{\mathrm{card}\{i\in\mathcal M\ |\ i\ \mathrm{even}\}}$ (because of the way the edges were directed above). After this, it follows from the construction of $\lambda_\gamma(\sigma)$ that $j_{2i}<j_{2i'}$ for all $i<i'$, and from the definition of $j_i$, $j_{2i-1}<j_{2i'-1}$ for all $i<i'$. By a positive-signature permutation, we can therefore reorder the sequence to +$$(j'_{|g|-|\mathcal M|+1},\cdots,j'_{|g|+|\mathcal M|})$$ +where $|\partial g|\ge j'_{|g|-|\mathcal M|+1}>\cdots>j'_{|g|}$ and $|g|<j'_{|g|+1}<\cdots<j'_{|g|+|\mathcal M|}$. Furthermore, +$$(j'_{|g|+1},\cdots,j'_{|g|+|\mathcal M|},j_{|g|+|\mathcal M|+1},\cdots,j_{|g|+|\epsilon|})$$ +can be ordered by a positive signature permutation (since $j_{2i}=j_{2i-1}+1$ for $i>(|g|+|\mathcal M|)/2$). Finally, +$$(j'_1,\cdots,j'_{|g|-|\mathcal M|},j'_{|g|-|\mathcal M|+1},\cdots,j'_{|g|})$$ +can be ordered by a permutation whose signature is $(-1)^{\mathrm{card}\{i\in\mathcal M\ |\ i\ \mathrm{odd}\}}$. By composing all of these permutations, we find that the sign of $\lambda_\gamma(\sigma)$ is +$$s(-1)^{\mathrm{card}\{i\in\mathcal M\ |\ i\ \mathrm{odd}\}}(-1)^{\mathrm{card}\{i\in\mathcal M\ |\ i\ \mathrm{even}\}}=s(-1)^{|\mathcal M|}=s.$$ +Therefore, the sign of $\sigma$ and the sign of $\lambda_\gamma(\sigma)$ are equal. +\medskip + +\indent We can now conclude the proof of the lemma. By construction, one of the bMD coverings of $g$, which we denote by $\Sigma$, is positive, which implies that $\lambda_\gamma(\Sigma)$ is positive, and therefore, by proposition~\ref{propkasteleyn}, that $\gamma$ is positive. For every dimer covering $\sigma$ of $[g]_{\mathcal M}$, $\lambda_\gamma(\sigma)$ is, therefore, positive, which implies that $\sigma$ is positive, and concludes the proof of the lemma.\qed + + +\section{Reducing generic planar graphs to enclosed graphs}\label{secreduce} +\indent 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} +\indent 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} +\bigskip + +\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} +\indent 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 -\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$ +\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} \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}''). +\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 +\indent Thanks go to Jan Philip Solovej and Lukas Schimmer for devoting their time to some preliminary calculations that helped put us on the right track. 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. In addition, 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 thank Jacques Perk and Fa Yueh Wu for very useful historical comments. -\section{Additional preliminaries}\label{secprelin} -\indent In this section, we discuss several properties which we will use to treat graphs that have vertices inside their boundary. +\indent 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.). +\vfill +\eject +\appendix -\subsection{Properties of Kasteleyn graphs}\label{subsecpropkasteleyn} -\indent In this section, we prove a few useful lemmas about Kasteleyn graphs. The key result is the following. +\section{Properties of Kasteleyn graphs}\label{apppropkasteleyn} +\indent In this appendix, we prove a few useful lemmas about Kasteleyn graphs. The key result is the following. \bigskip \theo{Lemma}\label{lemmacombcircuits} @@ -745,7 +748,7 @@ and $c_2$ are either both oddly-directed or both evenly-directed. \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$ +$c$, whereas the parity is different if $\nu$ is even.\qed \bigskip \indent Lemma \ref{lemmacombcircuits} has a number of useful consequences, which are discussed in the following. @@ -756,7 +759,7 @@ 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$ +lemma~\ref{lemmacombcircuits}.\qed \bigskip \theo{Lemma}\label{lemmakasteleynrmedge} @@ -765,7 +768,7 @@ 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$ +\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$.\qed \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. @@ -806,671 +809,15 @@ 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{figinnercov}. - -\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{figinnercov} -\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} -\indent 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} -\indent 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} -\indent 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 +hypothesis.\qed \bigskip -\indent Thanks go to Jan Philip Solovej and Lukas Schimmer for devoting their time to some preliminary calculations that helped put us on the right track. 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. In addition, 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 thank Jacques Perk and Fa Yueh Wu for very useful historical comments. -\indent 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.). -\vfill -\eject -\appendix \section{Examples}\label{appexamples} \indent In this appendix we provide some examples of Pfaffian formulas to illustrate the discussion. -\subsection{A simple graph} -\indent 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 +\subsection{A graph with no interior vertices} +\indent In this section, we compute the Pfaffian corresponding to figure~\ref{figsimpleexample}. We direct and label the graph as per the discussion in section~\ref{secenclosed} (see figure~\ref{figsimpleexample}). 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\\ @@ -1488,9 +835,17 @@ which is completed by antisymmetry. The MD partition function is therefore \Xi(x)=\mathrm{pf}(A(x))= x^4+11\,x^3+33\,x^2+28\,x+3. \label{eqsimpleexample}\end{equation} +\bigskip -\subsection{Another simple graph: the L-shape} -\indent 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) +\begin{figure} +\hfil\parbox[m]{3cm}{\includegraphics[width=3cm]{Figs/simple_example.pdf}} +\hfil\parbox[m]{3.8cm}{\includegraphics[width=3.8cm]{Figs/simple_example_labels.pdf}}\par\penalty10000 +\medskip +\captionshort{A graph with no interior vertices, and its direction and labeling.} +\label{figsimpleexample}\end{figure} + +\subsection{Another graph with no interior: the L-shape} +\indent 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{secenclosed} (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\\ @@ -1517,8 +872,8 @@ x^4+10\,x^3+28\,x^2+24\,x+4 \label{figLshape} \end{figure} -\subsection{An evenly filled graph} -\indent 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. +\subsection{A square graph} +\indent In this section, we compute the Pfaffian corresponding to the graph in figure~\ref{figevenexample}. 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\\ @@ -1541,6 +896,14 @@ The MD partition function is therefore \Xi(x)=\mathrm{pf}(A(x))= 2x^6 + 40x^5 + 256x^4 + 680x^3 + 776x^2 + 336x + 36. \label{eqevenexample}\end{equation} +\bigskip + +\begin{figure} +\hfil\parbox[m]{3cm}{\includegraphics[width=3cm]{Figs/even_example.pdf}} +\hfil\parbox[m]{3.8cm}{\includegraphics[width=3.8cm]{Figs/even_example_label.pdf}}\par\penalty10000 +\medskip +\captionshort{A square graph, and its direction and labeling.} +\label{figevenexample}\end{figure} \subsection{An enclosed graph} \indent 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. @@ -1648,7 +1011,7 @@ Both~(\ref{eqpfaff3x2}) and~(\ref{eqpfaff5x5}) are in agreement with the results \indent If a graph $g\in\mathcal G$ is {\it Hamiltonian}, i.e. if there exists a circuit, called a {\it Hamiltonian cycle}, that goes through every vertex of $g$ exactly once, then we will now show how to write the {\it full} MD partition function on $g$ as a product of two Pfaffians. The condition that $g$ is Hamiltonian, is not restrictive, since 0-weight edges and vertices can be added to $g$ to make it so. \medskip -Given a Hamiltonian cycle $c$, let $g_i$ denote the graph obtained from $g$ by removing every edge outside $c$ (that is the edges that are neither part of the Hamilton cycle, nor enclosed by it), and $\bar g_e$ the graph obtained from $g$ by removing every edge enclosed by $c$. We then consider a new embedding of $\bar g_e$, denoted by $g_e$, that is such that every vertex of $g_e$ is on the boundary (this is achieved by turning it inside out, that is, by setting the infinity-face of $g_e$ from the outside to the inside of the Hamilton cycle in $\bar g_e$). +\indent Given a Hamiltonian cycle $c$, let $g_i$ denote the graph obtained from $g$ by removing every edge outside $c$ (that is the edges that are neither part of the Hamilton cycle, nor enclosed by it), and $\bar g_e$ the graph obtained from $g$ by removing every edge enclosed by $c$. We then consider a new embedding of $\bar g_e$, denoted by $g_e$, that is such that every vertex of $g_e$ is on the boundary (this is achieved by turning it inside out, that is, by setting the infinity-face of $g_e$ from the outside to the inside of the Hamilton cycle in $\bar g_e$). \indent The monomer dimer-partition function of $g$ can then be computed in the following way. We first set the weights of the edges and vertices of $g_e$ and $g_i$: \begin{itemize} @@ -1675,6 +1038,7 @@ By theorem~\ref{theomain}, this implies the following theorem. \theoname{Theorem}{Pfaffian formula for the full MD partition function}\label{theofullmd} Given a Hamiltonian graph $g\in\mathcal G$, there exist two antisymmetric $|g|\times|g|$ matrices $A_i(\bm\lambda,\bm\delta)$ and $A_e(\bm\lambda,\bm\delta)$ such that +\nopagebreakaftereq \begin{equation}\begin{array}{r@{\ }>\displaystyle l} \Xi(\bm\ell,\mathbf d)=& \left(\prod_{v\in\mathcal V(g)}\left(1+\frac{\ell_v}2\frac{\partial^2}{\partial\lambda_v^2}\right)\right) @@ -1683,6 +1047,7 @@ Given a Hamiltonian graph $g\in\mathcal G$, there exist two antisymmetric $|g|\t \mathrm{pf}(A_i(\bm\lambda,\bm\delta))\mathrm{pf}(A_e(\bm\lambda,\bm\delta))\right|_{\bm\lambda=0,\,\bm\delta=0}. \end{array}\label{eqfullmdprodpf}\end{equation} \endtheo +\restorepagebreakaftereq \bigskip \indent The matrices $A_i$ and $A_e$ are constructed by directing and labeling $g_i$ and $g_e$ as in theorem~\ref{theomain}. @@ -1705,8 +1070,64 @@ Given a Hamiltonian graph $g\in\mathcal G$, there exist two antisymmetric $|g|\t \label{equpperbound}\end{equation} is a Laurent polynomial in $\sqrt{\ell_v}$, each of whose coefficients are larger or equal to the corresponding term in the MD partition function $\Xi(\bm\ell,\mathbf d)$. \endtheo + +\section{The bijection method}\label{appbijectionmethod} +\indent In this appendix, we show how to obtain an alternative Pfaffian formula for the boundary MD partition function via the {\it bijection method}. This construction was pointed out to us by an anonymous referee. It is related to the discussion in [\cite{Ku94}, section 4]. + +\subsection{Description of the method} +\indent The main idea is to use the auxiliary graph $\gamma$ introduced in the proof of lemma~\ref{lemmaenclosedpositivity}, and show that the boundary MD partition function on $g$ is equal to half of the pure dimer partition function on $\gamma$, provided the edges of $\gamma$ are weighted appropriately. We set the weights of the edges of $\gamma$ in the following way: +\begin{itemize} +\item every edge of $\gamma$ that is also an edge of $g$ has the same weight as in $g$, +\item every edge of $\epsilon$ (see the proof of lemma~\ref{lemmaenclosedpositivity} for the definition of $\epsilon$) is assigned weight 1, +\item an edge between a vertex $v\in\mathcal V(\partial g)$ and a vertex $v'\in\mathcal V(\epsilon)$ is assigned the weight $\ell_v$. +\end{itemize} + +\indent We define a map $\Lambda_\gamma$ which maps a pure dimer covering of $\gamma$ to a bMD covering of $g$. Given a dimer covering $\Sigma$ of $\gamma$, we construct $\Lambda_\gamma(\Sigma)$ by putting monomers on the vertices of $\partial g$ that are occupied by a dimer of $\Sigma$ whose other end-vertex is in $\epsilon$, and by putting dimers on the edges of $g$ that are occupied by a dimer in $\Sigma$. Obviously, the weight of $\Sigma$ is equal to the weight of $\Lambda_\gamma(\Sigma)$. + +\indent Note that the map $\lambda_\gamma$ defined in the proof of lemma~\ref{lemmaenclosedpositivity} satisfies $\Lambda_\gamma(\lambda_\gamma(\sigma))=\sigma$ for every bMD covering $\sigma$ of $g$. Furthermore, we define another map $\bar\lambda_\gamma$ from the bMD coverings of $g$ to the dimer coverings of $\gamma$, similarly to $\lambda_\gamma$, but with $p_j$ replaced by $p_j+1$ (see the proof of lemma~\ref{lemmaenclosedpositivity}). This map also satisfies $\Lambda_\gamma(\bar\lambda_\gamma(\sigma))=\sigma$ for every bMD covering $\sigma$ of $g$. In addition, one easily checks that $\lambda_\gamma(\sigma)\neq\bar\lambda_\gamma(\sigma)$. \bigskip +\indent We wish to prove that for every bMD covering $\sigma$ of $g$, there are exactly two distinct pure dimer coverings $\Sigma_1$ and $\Sigma_2$ of $\gamma$ that satisfy $\Lambda_\gamma(\Sigma_i)=\sigma$. This is obvious if $\sigma$ has no monomers, so we will assume that $\sigma$ has at least one monomer, located on the vertex labeled as 1. Let $\sigma$ be such a covering. The coverings $\lambda_\gamma(\sigma)$ and $\bar\lambda_\gamma(\sigma)$ satisfy the required condition. One can then easily show, by induction, that having fixed a dimer on $\{\omega^{-1}_\gamma(1),\omega^{-1}_\gamma(|g|+1)\}$ as in $\lambda_\gamma(\sigma)$, $\lambda_\gamma(\sigma)$ is the {\it only} dimer covering of $\gamma$ that satisfies $\Lambda_\gamma(\lambda_\gamma(\sigma))=\sigma$. A similar argument can be made for $\bar\lambda_\gamma(\sigma)$. This implies that $\lambda_\gamma(\sigma)$ and $\bar\lambda_\gamma(\sigma)$ are the only dimer coverings of $\gamma$ satisfying $\Lambda(\Sigma_i)=\sigma$. + +\indent In conclusion, the bMD partition function on $g$ is equal to half of the pure dimer partition function on $\gamma$. By Kasteleyn's theorem, the bMD partition function can, therefore, be written as a Pfaffian. + + +\subsection{Example} +\indent Let us look at a simple example and see how the Pfaffian formula one obtains from the bijection method differs from that presented in theorem~\ref{theomain}. + +\indent Consider the square graph (see figure~\ref{figsquare}). Using the bijection method, we find that the bMD partition function on the square graph at dimer fugacity 1 and monomer fugacity $z$ is +\begin{equation} +\Xi_\partial=\frac12\mathrm{pf}\left(\begin{array}{cccccccc} +0 & 1& 0& 1& z& 0& 0&-z\\ +-1& 0& 1& 0&-z&-z& 0& 0\\ + 0&-1& 0& 1& 0& z& z& 0\\ +-1& 0&-1& 0& 0& 0&-z&-z\\ +-z& z& 0& 0& 0& 1& 0& 1\\ + 0& z&-z& 0&-1& 0& 1& 0\\ + 0& 0&-z& z& 0&-1& 0& 1\\ + z& 0& 0& z&-1& 0&-1& 0 +\end{array}\right).\label{eqsquarebijection}\end{equation} +Using theorem~\ref{theomain}, we find +\begin{equation} +\Xi_\partial=\mathrm{pf}\left(\begin{array}{cccc} + 0& 1+z^2& -z^2& 1+z^2\\ +-1-z^2& 0& 1+z^2& -z^2\\ + z^2&-1-z^2& 0& 1+z^2\\ +-1-z^2& z^2&-1-z^2& 0 +\end{array}\right).\label{eqsquare}\end{equation} +Obviously, both formulas yield the same result: +\begin{equation} +\Xi_\partial=z^4+4z^2+2. +\label{eqsquareres}\end{equation} + +\begin{figure} +\hfil\parbox[m]{2cm}{\includegraphics[width=2cm]{Figs/square.pdf}} +\hfil\parbox[m]{6cm}{\includegraphics[width=6cm]{Figs/square_auxiliary.pdf}}\par\penalty10000 +\medskip +\captionshort{The square graph and the associated auxiliary graph $\gamma$.} +\label{figsquare}\end{figure} + + \vfill \eject diff --git a/bibliography.BBlog.tex b/bibliography.BBlog.tex index 3eeb760..9e3b77b 100644 --- a/bibliography.BBlog.tex +++ b/bibliography.BBlog.tex @@ -23,6 +23,7 @@ \BBlogentry{Ke01}{Ke01}{R. Kenyon - {\it Dominos and the Gaussian free field}, The Annals of Probability, Vol.~29, n.~3, p.~1128-1137, 2001.} \BBlogentry{Ko06c}{Ko06}{Y. Kong - {\it Monomer-dimer model in two-dimensional rectangular lattices with fixed dimer density}, Physical Review E, Vol.~74, n.~061102, 2006.} \BBlogentry{Kr06}{Kr06}{W. Krauth - {\it Statistical mechanics: Algorithms and computations}, Oxford Masters Series in Statistical, Computational, and Theoretical Physics, Oxford University Press, 2006.} +\BBlogentry{Ku94}{Ku94}{G. Kuperberg - {\it Symmetries of plane partitions and the permanent-determinant method}, Journal of Combinatorial Theory, Series A, Vol.~68, n.~1, p.~115-151, 1994, doi:{\tt\color{blue}\href{http://dx.doi.org/10.1016/0097-3165(94)90094-9}{10.1016/0097-3165(94)90094-9}}.} \BBlogentry{Li67}{Li67}{E.H. Lieb - {\it Solution of the dimer problem by the transfer matrix method}, Journal of Mathematical Physics, Vol.~8, n.~12, p.~2339-2341, 1967, doi:{\tt\color{blue}\href{http://dx.doi.org/10.1063/1.1705163}{10.1063/1.1705163}}.} \BBlogentry{Li68}{Li68}{E.H. Lieb - {\it A theorem on Pfaffians}, Journal of Combinatorial Theory, Vol.~5, p.~313-319, 1968, doi:{\tt\color{blue}\href{http://dx.doi.org/10.1016/S0021-9800(68)80078-X}{10.1016/S0021-9800(68)80078-X}}.} \BBlogentry{LL93}{LL93}{E.H. Lieb, M. Loss - {\it Fluxes, Laplacians, and Kasteleyn's Theorem}, Duke Mathematical Journal, Vol.~71, n.~2, p.~337-363, 1993.} diff --git a/iansecs.sty b/iansecs.sty index 8d1cc9f..1eb65c8 100644 --- a/iansecs.sty +++ b/iansecs.sty @@ -40,16 +40,6 @@ \eject } -%% prevent page breaks -\newcount\prevpostdisplaypenalty -\def\nopagebreakaftereq{ - \prevpostdisplaypenalty=\postdisplaypenalty - \postdisplaypenalty=10000 -} -\def\restorepagebreakaftereq{ - \postdisplaypenalty=\prevpostdisplaypenalty -} - %% hyperlinks % hyperlinkcounter \newcounter{lncount} diff --git a/toolbox.sty b/toolbox.sty index 7f5738e..5713be0 100644 --- a/toolbox.sty +++ b/toolbox.sty @@ -34,6 +34,17 @@ \@beginparpenalty=\prevparpenalty } +%% prevent page breaks after displayed equations +\newcount\prevpostdisplaypenalty +\def\nopagebreakaftereq{ + \prevpostdisplaypenalty=\postdisplaypenalty + \postdisplaypenalty=10000 +} +%% back to previous value +\def\restorepagebreakaftereq{ + \postdisplaypenalty=\prevpostdisplaypenalty +} + %% stack relations in subscript or superscript \def\mAthop#1{\displaystyle\mathop{\scriptstyle #1}} @@ -44,3 +55,5 @@ \def\largearray{\begin{array}{@{}>{\displaystyle}l@{}}\hphantom{\hspace{\largearray@width}}\\[-.5cm]} \def\endlargearray{\end{array}} +%% qedsquare +\def\qed{\penalty10000\hfill\penalty10000$\square$} |