From b1f41821ba2a79274891d0016df4916454c24f9c Mon Sep 17 00:00:00 2001 From: Ian Jauslin Date: Wed, 21 Oct 2015 14:47:08 +0000 Subject: Addition: algorithm for full MD partition function using 2 Pfaffians Addition: upper bound on full MD partition function Comment: extension of algorithms for full MD partition function on non-planar graphs Formatting errors and punctuation in labels --- Giuliani_Jauslin_Lieb_2015.tex | 111 +++++++++++++++++++++++++++++++++-------- iansecs.sty | 17 +------ 2 files changed, 91 insertions(+), 37 deletions(-) diff --git a/Giuliani_Jauslin_Lieb_2015.tex b/Giuliani_Jauslin_Lieb_2015.tex index d383c37..6afdf9d 100644 --- a/Giuliani_Jauslin_Lieb_2015.tex +++ b/Giuliani_Jauslin_Lieb_2015.tex @@ -144,12 +144,14 @@ and $A_{j,i}(\bm\ell,\mathbf d):=-A_{i,j}(\bm\ell,\mathbf d)$, the boundary MD p \item Similarly, by setting edge weights to 0, dimers can be excluded from any part of the graph. \item It may be worth noting that the weights $d_e$ and $\ell_v$ may be complex. \item Our result provides a polynomial-time algorithm for computing boundary MD partition functions on generic planar graphs. -See appendix \ref{app.A} for examples. -\item Based on theorem \ref{theomain}, we have derived an algorithm (see appendix~\ref{appalg}) that allows us to compute the {\it full} MD partition function (as opposed to the boundary MD partition function) on an arbitrary planar graph, which is more efficient than the naive enumeration algorithm. +See appendix \ref{appexamples} for examples. +\item Based on theorem \ref{theomain}, we have derived an algorithm (see appendix~\ref{appalg}) that allows us to compute the {\it full} MD partition function (as opposed to the boundary MD partition function) on an arbitrary graph (which is not necessarily planar), which is more efficient than the naive enumeration algorithm. For instance, if $g$ is an $L\times M$ rectangle on the square lattice, our algorithm requires $O((LM)^3 2^{(LM)/2})$ operations, while the naive algorithm requires $O((LM)^32^{LM})$. In the rectangular case, a transfer matrix approach would be even faster, completing the computation in $O((LM)^32^L)$ operations~[\cite{Ko06c}], but our algorithm does not require the graph to be treatable via a transfer matrix approach. +\item In addition, we have developed an alternative algorithm (see appendix~\ref{appinout}) to express the {\it full} MD partition function on Hamiltonian planar graphs as a derivative of the product of just two Pfaffians. From a computational point of view, this approach is even slower than the previous one, but it is nonetheless conceptually interesting. Note that this algorithm can be adapted to non-planar graphs as well. +\item Finally, we have also computed upper and lower bounds for the {\it full} partition function, see theorems~\ref{theolowerbound} and~\ref{theoupperbound}. \item As a side remark, note that Monte Carlo methods methods can be even faster, i.e., polynomial in the size of the system~[\cite{KRS96}], but they provide correct results only with high probability rather than with certainty. \end{itemize} \unlistparpenalty @@ -220,12 +222,12 @@ and reduces it to the previous case. \section{Preliminaries}\label{secpreliminaries} -In this section, we present the key results that will allow us to prove the +\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}. \bigskip \subsection{Kasteleyn's theorem}\label{subseckasteleyn} -In this section, we discuss a method introduced by P.~Kasteleyn [\cite{Ka63}] +\indent In this section, we discuss a method introduced by P.~Kasteleyn [\cite{Ka63}] to write the partition function of dimers on planar graphs as a Pfaffian. In order to construct the matrix $A$ whose Pfaffian yields the partition function of dimers, the graph $g$ must first be oriented and its vertices @@ -497,6 +499,10 @@ In other words, the coefficient of $\ell_{i_1}\cdots\ell_{i_k}$ is a lower bound for the number of dimer coverings with monomers at $i_1,\cdots,i_k$. \endtheo \bigskip +\bigskip + +{\bf Remark}: An upper bound for the MD partition function is provided in theorem~\ref{theoupperbound}. +\bigskip \point{\bf Proof of corollary \ref{corrmain}.} Corollary~\ref{corrmain} follows easily from theorems~\ref{theomain} and~\ref{theolieb}. Indeed, by~(\ref{eqtheo}) and~(\ref{eqliebtheo}), @@ -675,11 +681,11 @@ By theorem~\ref{theolieb}, this implies theorem \ref{theomain} for simple graphs, provided $g\in\mathcal G_s$ is directed and labeled as above (see ``\ref{recipesimple}''). \section{Additional preliminaries}\label{secprelin} -In this section, we discuss several properties which we will use to treat graphs that have vertices inside their boundary. +\indent In this section, we discuss several properties which we will use to treat graphs that have vertices inside their boundary. \subsection{Properties of Kasteleyn graphs}\label{subsecpropkasteleyn} -In this section, we prove a few useful lemmas about Kasteleyn graphs. The key result is the following. +\indent In this section, we prove a few useful lemmas about Kasteleyn graphs. The key result is the following. \bigskip \theo{Lemma}\label{lemmacombcircuits} @@ -1038,7 +1044,7 @@ For every $x\alpha\in \epsilon(\sigma)$ we define an ordered set $x\bar\alpha$ containing $x\alpha$ and the labels $x\beta\in\iota_x(\sigma)$, which are such that, if $(x\beta,x\beta')$ is a dimer and $x\beta,x\beta'\in x\bar\alpha$, then $x\tau_{\beta,\beta'}\in x\bar\alpha$. The ordering of $x\bar\alpha$ is that inherited from $\sigma$. The set $x\bar\alpha$ can either be {\it trivial}, if it has only one element (in which case $x\bar\alpha=(x\alpha)$), -or it can be of three possible non-trivial types, depicted in figure~\ref{fig:4.7}. +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 @@ -1055,7 +1061,7 @@ where $k,k'\ge 0$, $k+k'$ is even and $[\alpha+i]$ is the character-wise additio \caption{The three possible types of non-trivial sets $x\bar\alpha$, and their corresponding dimer covering. In each of these, the labels of the vertices covered by dimers can be written as $(x[\alpha-k],\ldots,x\alpha,\ldots, x[\alpha+k'])$. In the first case, $k,k'$ are both odd. In the second case, $k$ is positive and even, while $k'=0$. In the third case, $k=0$, while $k'$ is positive and even. In addition to these types, $x\bar\alpha$ could be trivial, that is $k=k'=0$.} -\label{fig:4.7} +\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 @@ -1400,10 +1406,10 @@ which, by theorem~\ref{theolieb}, implies theorem \ref{theomain} for enclosed graphs, provided $g\in\mathcal G_{en}$ is directed and labeled as above (see ``\ref{recipeenclosed}''). \section{Reducing generic planar graphs to enclosed graphs}\label{sec7} -In this section, we discuss how a generic planar graph can be reduced to an enclosed graph. In particular, we will show how to add 0-weight edges to a graph to construct a boundary circuit, and how to add 0-weight edges and vertices to a graph that has an odd number of vertices in its boundary circuit to turn it into an enclosed graph, for which theorem~\ref{theomain} was proved in section~\ref{secenclosed}. +\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} -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$. +\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. @@ -1426,7 +1432,7 @@ By construction, $(v_{i_1},\cdots,v_{i_k})$ is the boundary circuit of the resul \indent Once the boundary circuit has been constructed, if the boundary circuit contains an even number of vertices, then the resulting graph is an enclosed graph and can be directed and labeled as in section~\ref{secenclosed}. If the boundary circuit contains an odd number of vertices then the graph can be further reduced to an enclosed graph as explained in the following section. \subsection{Making a boundary circuit even}\label{secevenboundarycircuit} -In this section, we show how to add edges and vertices to a graph with a boundary circuit that contains an odd number of vertices to an enclosed graph, in such a way that the boundary MD partition function is unchanged. The procedure is simple: pick an edge of the boundary circuit, and +\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 @@ -1452,11 +1458,11 @@ We also would like to thank Tom Spencer and Joel Lebowitz for their hospitality \eject \appendix -\section{Examples}\label{app.A} -In this appendix we provide some examples of Pfaffian formulas to illustrate the discussion. +\section{Examples}\label{appexamples} +\indent In this appendix we provide some examples of Pfaffian formulas to illustrate the discussion. \subsection{A simple graph} -In this section, we compute the Pfaffian corresponding to the first graph of figure~\ref{figsimpleexample}, directed and labeled as in figure~\ref{figsimpleexamplelabels}. We set the edge weights $d_e=1$ and assume the monomer weights $\ell_i$ are all equal to $\sqrt{x}$. The antisymmetric matrix $A(\bm\ell,\mathbf d)$ is +\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 $$ A(x)=\left(\begin{array}{cccccccc} 0&1+x&-x&x&-x&x&-x&1+x\\ @@ -1476,7 +1482,7 @@ x^4+11\,x^3+33\,x^2+28\,x+3. \label{eqsimpleexample}\end{equation} \subsection{Another simple graph: the L-shape} -In this section we compute the MD partition function for another simple graph: the {\it L-shape}, represented in figure~\ref{figLshape}. We direct and label the graph as per the discussion in section~\ref{secsimple} (see figure~\ref{figLshape}) and find (setting $d_v=1$ and $\ell_i=\sqrt{x}$ as before) +\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) $$ A(x)=\left(\begin{array}{cccccccc} 0&1+x&-x&x&-x&x&-x&1+x\\ @@ -1504,7 +1510,7 @@ x^4+10\,x^3+28\,x^2+24\,x+4 \end{figure} \subsection{An evenly filled graph} -In this section, we compute the Pfaffian corresponding to the graph in figure~\ref{figevenexample}, directed and labeled as in figure~\ref{figevenexamplelabels}. We set $d_e=1$ and $\ell_i=\sqrt{x}$. Since the expression of the matrix $A$ is rather long, we split it into lines and only write the $i\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) +\left(\prod_{e\in\mathcal E(c)}\left(1+\frac{d_e}2\frac{\partial^2}{\partial\delta_e^2}\right)\right)\cdot\\[1cm] +&\left.\cdot\left(\prod_{e=\{v,v'\}\in\mathcal E(g)\setminus\mathcal E(c)}\left(1+d_e\frac{\partial^3}{\partial\delta_e\partial\lambda_v\partial\lambda_{v'}}\right)\right) +\Xi_i(\bm\lambda,\bm\delta)\Xi_e(\bm\lambda,\bm\delta)\right|_{\bm\lambda=0,\,\bm\delta=0}. +\end{array}\label{eqfullmdprodXi}\end{equation} +By theorem~\ref{theomain}, this implies the following theorem. +\bigskip + +\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 +\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) +\left(\prod_{e\in\mathcal E(c)}\left(1+\frac{d_e}2\frac{\partial^2}{\partial\delta_e^2}\right)\right)\cdot\\[1cm] +&\left.\cdot\left(\prod_{e=\{v,v'\}\in\mathcal E(g)\setminus\mathcal E(c)}\left(1+d_e\frac{\partial^3}{\partial\delta_e\partial\lambda_v\partial\lambda_{v'}}\right)\right) +\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 +\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}. +\bigskip + +{\bf Remark}: It is important to note that this does not contradict the intractability result of M.~Jerrum~[\cite{Je87}]: indeed, (\ref{eqfullmdprodpf}) cannot, in general, be computed in polynomial-time. Indeed, since the entries of $A_i$ and $A_e$ are polynomials of $|g|+|\mathcal E(g)|$ variables, and computing their Pfaffian requires $O(|g|^3)$ multiplications of such elements, the computation of $\Xi$ via~(\ref{eqfullmdprodpf}) requires $O(|g|^32^{|g|+|\mathcal E(g)|})$ operations. This result extends to the Pfaffian formula in theorem~\ref{theomain}, but, there, if the weights $\ell_v$ and $d_e$ are given numerical values, or set to be equal among each other, the computation of the Pfaffian in~(\ref{eqtheo}) can be performed in polynomial-time. Because of the presence of derivatives in~(\ref{eqfullmdprodpf}), a similar operation cannot be done to compute~(\ref{eqfullmdprodpf}) in polynomial-time. +\bigskip + +\indent From theorem~\ref{theofullmd}, one can easily prove the following upper bound on the full MD partition function, which complements the lower bound in theorem~\ref{theolowerbound}. +\bigskip + +\theoname{Theorem}{Upper bound for the terms in the MD partition function}\label{theoupperbound} +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, if $d_e\ge0$ and $\ell_v>0$ for all $(v,e)\in\mathcal V(g)\times\mathcal E(g)$, the product +\begin{equation} +\mathrm{pf}(A_i(\bm\lambda,\bm\delta))\mathrm{pf}(A_e(\bm\lambda,\bm\delta))\Big|_{\begin{array}{>\scriptstyle l} +\lambda_v=\sqrt{\ell_v}\\ +\delta_e=\sqrt{d_e}\,\mathrm{if}\,e\in\mathcal E(c)\\ +\delta_e=\sqrt{d_e}\sqrt{\ell_v\ell_{v'}}^{-1}\,\mathrm{if}\,e=\{v,v'\}\not\in\mathcal E(c) +\end{array}} +\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 +\bigskip + \vfill \eject diff --git a/iansecs.sty b/iansecs.sty index 04ffdd0..2720942 100644 --- a/iansecs.sty +++ b/iansecs.sty @@ -407,22 +407,7 @@ \let\endtheo\enddelim %% theorem headers with name \def\theoname#1#2{ - \stepcounter{Theocount} - % reset points - \ifresetpointattheo\resetpointcounter\fi - % hyperref anchor - \hrefanchor - % the number - \def\formattheo{\theTheocount} - % add section number - \ifsections - \let\tmp\formattheo - \edef\formattheo{\sectionprefix\thesectioncount.\tmp} - \fi - % define tag (for \label) - \xdef\tag{\formattheo} - % write - \delimtitle{\bf #1 \formattheo\ \rm(\it #2\rm)} + \theo{#1}\hfil({\it #2})\par\penalty10000\medskip% } %% start appendices -- cgit v1.2.3-54-g00ecf