diff options
Diffstat (limited to 'Giuliani_Jauslin_Lieb_2015.tex')
| -rw-r--r-- | Giuliani_Jauslin_Lieb_2015.tex | 111 |
1 files changed, 90 insertions, 21 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<j$ terms. +\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. $$\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\\ @@ -1529,7 +1535,7 @@ The MD partition function is therefore \label{eqevenexample}\end{equation} \subsection{An enclosed graph} -In this section, we compute the Pfaffian corresponding to the graph in figure~\ref{figenclosedexample}, directed and labeled as in figure~\ref{figenclosedexamplecover}. We set $d_e=1$ and $\ell_i=\sqrt{x}$. Since the expression of the matrix $A$ is rather long, we split it into lines and only write the $i<j$ terms. +\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. $$\begin{array}{r@{\ }r} A_{ 1,\cdot}(x)=& 1+x, -x, x, -x, x, -x, 1+x, 0, 0, 0, 0, 1 , 0, 0,-1 \\ A_{ 2,\cdot}(x)=& 1+x, -x, x, -x, x, -x, 0, 0, 0, 0, 0, 0, 0, 0\\ @@ -1554,7 +1560,7 @@ The MD partition function is therefore \label{eqenclosedexample}\end{equation} \subsection{A graph with no boundary circuit} -In this section, we compute the Pfaffian corresponding to the graph in figure~\ref{figboundaryexample}, directed and labeled as in figure~\ref{figboundaryexampledir}. We set $d_e=1$ and $\ell_i=\sqrt{x}$. Since the expression of the matrix $A$ is rather long, we split it into lines and only write the $i<j$ terms. +\indent In this section, we compute the Pfaffian corresponding to the graph in figure~\ref{figboundaryexample}, directed and labeled as in figure~\ref{figboundaryexampledir}. We set $d_e=1$ and $\ell_i=\sqrt{x}$. Since the expression of the matrix $A$ is rather long, we split it into lines and only write the $i<j$ terms. $$\begin{array}{r@{\ }r} A_{ 1,\cdot}(x)=& 1+x, -x, x, -x, x, -x, x, -x, x, -x, x,-1-x, 1 , 0, 0\\ A_{ 2,\cdot}(x)=& 1+x, -x, x, -x, x, -x, x, -x, x, -x, 1+x, 1 , 0, 0\\ @@ -1588,10 +1594,9 @@ The MD partition function is therefore \section{An algorithm for the full monomer-dimer partition function} \label{appalg} -\indent In this appendix, we discuss an algorithm to compute the {\it full} MD partition function on an arbitrary planar graph. - -\indent The main idea is to isolate a {\it skeleton} $s$ from the graph, which is a sub-graph of $g$ obtained by removing edges from $g$ in such a way that $s$ contains no internal vertices. The boundary MD partition function of $s$ is the partition function of MD coverings of $g$ that does not have any dimers outside the skeleton. In order to count the coverings that do have dimers outside the skeleton, we add the following terms to the partition function. For every collection $\sigma$ of dimers that occupy edges that are outside the skeleton, we construct a sub-graph $[s]_\sigma$ of $s$ by removing the vertices covered by a dimer in $\sigma$. The boundary MD partition function of this sub-graph can be computed using theorem~\ref{theomain}. The full MD partition function is then obtained by summing the boundary MD partition functions of every such $[s]_\sigma$. +\indent In this appendix, we discuss an algorithm to compute the {\it full} MD partition function on an arbitrary graph (which is not necessarily planar). +\indent The main idea is to isolate a {\it skeleton} $s$ from the graph, which is a sub-graph of $g$ obtained by removing edges from $g$ in such a way that $s$ is planar and contains no internal vertices. The boundary MD partition function of $s$ is the partition function of MD coverings of $g$ that does not have any dimers outside the skeleton. In order to count the coverings that do have dimers outside the skeleton, we add the following terms to the partition function. For every collection $\sigma$ of dimers that occupy edges that are outside the skeleton, we construct a sub-graph $[s]_\sigma$ of $s$ by removing the vertices covered by a dimer in $\sigma$. The boundary MD partition function of this sub-graph can be computed using theorem~\ref{theomain}. The full MD partition function is then obtained by summing the boundary MD partition functions of every such $[s]_\sigma$. \bigskip \indent If $g$ is an $L\times M$ sub-rectangle of $\mathbb Z^2$ with, say, $L$ even, then the skeleton can be constructed as in figure~(\ref{figskeleton}). By this algorithm, the MD partition function can be computed by summing $2^{\frac12(L-2)(M-2)}$ Pfaffians. @@ -1630,6 +1635,70 @@ Both~(\ref{eqpfaff3x2}) and~(\ref{eqpfaff5x5}) are in agreement with the results \label{figalgexample1} \end{figure} +\section{Another algorithm for the full monomer-dimer partition function} +\label{appinout} +\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 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} +\item given a vertex $v\in\mathcal V(g)$, we denote the weight of $v$ in $g_i$ by $\lambda_v$, and set the weight of $v$ in $g_e$ to the same value $\lambda_v$, +\item for every edge $e\in\mathcal E(c)$ that is part of the Hamilton cycle $c$, we denote the weight of $e$ in $g_i$ by $\delta_e$ and set the weight of $e$ in $g_e$ to the same value $\delta_e$, +\item for every edge $e\in\mathcal E(g)\setminus\mathcal E(c)$ that is {\it not} part of the Hamilton cycle $c$, $e$ is either an edge of $g_i$ or an edge of $g_e$; in either case, its weight is denoted by $\delta_e$. +\end{itemize} +Let $\Xi_i$ and $\Xi_e$ be the boundary MD partition functions on $g_i$ and $g_e$ respectively. The function $\Xi_i\Xi_e$ is a polynomial of order 2 in $\lambda_v$ and $\delta_e$. The terms in $\Xi_i\Xi_e$ that correspond to an MD covering of $g$ are those in which the corresponding coverings of $g_i$ and $g_e$ satisfy the following conditions: +\begin{itemize} +\item an edge $e\in\mathcal E(c)$ is occupied by a dimer in $g_i$ if and only if it is occupied in $g_e$ as well, +\item an edge $e=\{v,v'\}\in\mathcal E(g)\setminus\mathcal E(c)$ is occupied by a dimer in $g_i$ if and only if $v$ and $v'$ are occupied by monomers in $g_e$, and vice-versa, +\item a vertex $v\in\mathcal V(g)$ that is not covered by a dimer on $\mathcal E(g)\setminus\mathcal E(c)$, is occupied by a monomer in $g_i$ if and only if it is occupied in $g_e$ as well. +\end{itemize} +Therefore +\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) +\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 |