\magnification=1200
\def\qed{\unskip\kern 6pt\penalty 500\raise -2pt\hbox
{\vrule\vbox to 10pt{\hrule width 4pt\vfill\hrule}\vrule}}
\centerline{ZEROS OF GRAPH-COUNTING POLYNOMIALS.}
\bigskip
\centerline{by David Ruelle\footnote{*}{IHES.  91440 Bures sur Yvette,
France. $<$ruelle@ihes.fr$>$}.}
\bigskip\bigskip\noindent
	{\leftskip=2cm\rightskip=2cm\sl Abstract.  Given a finite graph $E$ we define a family ${\cal A}$ of subgraphs $F$ by restricting the number of edges of $F$ with endpoint at any vertex of $E$.  Defining $Q_{\cal A}(z)=\sum_{F\in {\cal U}}z^{{\rm card}F}$, we can in many cases give precise information on the location of zeros of $Q_{\cal A}(z)$ (zeros all real negative, all imaginary, etc.).  Extensions of these results to weighted and infinite graphs are given.\par}
\bigskip\bigskip
	{\bf 1. Introduction and statement of results.}
\medskip
	This paper studies the location of zeros of polynomials 
$$	Q_{\cal A}(z)=\sum_{F\in {\cal A}}z^{{\rm card}F}\eqno{(1.1)}      $$
where ${\cal A}$ is a set of subgraphs of a given finite graph $(V,E)$.  The {\it graph} $(V,E)$ is defined by the vertex set $V$, the edge set $E$, and the two endpoints $j$, $k\in V$ of each $a\in E$ (we assume $j\ne k$, but allow several edges with the same endpoints).  A {\it subgraph} $F$ is viewed as a subset of $E$.  We shall consider sets ${\cal A}$ of the general form 
$$	{\cal A}=\{F\subset E:(\hbox{restrictions on the numbers 
	of edges of $F$ with any endpoint }j\in V)\}      $$
We may write ${\cal A}={\cal A}(V,E)$ to indicate the dependence on the graph $(V,E)$.
\medskip
	Let $\sigma=\{\ldots\}$ be a set of nonnegative integers (we shall consider the cases $\sigma=\{0,1\}$, $\{1,2\}$, $\{0,1,2\}$, $\{0,2\}$, $\{0,2,4\}$, $\{{\rm even}\}$, $\{{\ge1}\}$, and also $\{<{\rm max}\}$ as explained below).  A set ${\cal A}=(\sigma)=(\{\ldots\})$ of subgraphs of $(V,E)$ is defined by
$$	{\cal A}=(\sigma)=\{F\subset E:(\forall j)\,{\rm card}\{a\in F:j
	\hbox{ is an endpoint of } a\}\in\sigma\}\eqno{(1.2)}      $$
In the case $\sigma=\{<{\rm max}\}$, the set $\sigma$ depends on $j$ and is
$$	\{<{\rm max}\}=\{s\ge0:s<\hbox{number of edges of $E$ 
	with endpoint $j$}\}      $$
\par
	Suppose that the graph $(V,E)$ is {\it oriented} by placing an arrow on each edge $a\in E$; at each vertex $j\in V$ there are thus {\it ingoing} and {\it outgoing} edges.  Given two sets $\sigma'$, $\sigma''$ of nonnegative integers we define 
$$	{\cal A}=(\sigma'\to\sigma'')=\{F\subset E:(\forall j)\,
	{\rm card}\{\hbox{outgoing edges of $F$ at $j$}\}\in \sigma'      $$
$$	\hbox{ and }{\rm card}\{\hbox{ingoing edges of $F$ at $j$}\}
	\in \sigma''\}\eqno{(1.3)}      $$
\par
	In the cases ${\cal A}=(\{\ldots\})$ and ${\cal A}=(\{\ldots\}\to\{\ldots\})$ as just defined, we impose the same restrictions at each vertex $j\in V$ and each edge $a\in E$.  One could consider more general situations where several classes of vertices and edges are distinguished , and also study them by the methods of this paper.  For simplicity we restrict ourselves to (1.2) and (1.3).
\medskip
	Some of our results on the location of the zeros $Z$ of $Q_{(\sigma'\to\sigma'')}$ are summarized in the following table.  For $Q_{(\sigma)}$ we obtain the same results as for $Q_{(\sigma\to\sigma)}$.  Much more precise statements will be made below in Section 6 for $(\sigma)$ and in Section 7 for $(\sigma'\to\sigma'')$.  Note also that the table may be completed by symmetry (the entry for $(\sigma'\to\sigma'')$ is the same as for $(\sigma''\to\sigma')$).	
$$\vbox{
	\def\ivl{\vrule height 12pt depth 5pt width 0pt}
	\def\vl{\ivl\vrule}
	\offinterlineskip\halign{
\hfill\enspace$#$\hfill\enspace\vl&\hfill\enspace$#$\hfill\enspace\vl&
\hfill\enspace$#$\hfill\enspace\vl&\hfill\enspace$#$\hfill\enspace\vl&
\hfill\enspace$#$\hfill\enspace\vl&\hfill\enspace$#$\hfill\enspace\vl\cr
&\{0,1\}&\{0,1,2\}&\{0,2\}\quad\{0,2,4\}\quad\{{\rm even}\}
	&\{<{\rm max}\}&\{\ge1\}\cr
\noalign{\hrule}
\{0,1\}&Z\enspace{\rm real}&{\rm Re}Z<0&Z\enspace{\rm imaginary}	&{\rm Re}Z<0&(Z=0)\cr
\noalign{\hrule}
\{0,1,2\}&&{\rm Re}Z<0&{\rm Re}Z^2<0&-&-\cr
\noalign{\hrule}
\{0,2\}&&&&&\cr
\{0,2,4\}&&&-&{\rm Im}Z\ne0&-\cr
\{{\rm even}\}&&&&&\cr
\noalign{\hrule}
\{<{\rm max}\}&&&&-&-\cr
\noalign{\hrule}\{\ge1\}&&&&&{\rm (cardioid)}\cr
\noalign{\hrule}
}}$$
\par
	The polynomial $Q_{(\{0,1\})}$ counts {\it dimer} subgraphs; the fact that its zeros are real (and therefore negative) was first proved by Heilmann and Lieb [3]\footnote{*}{For a generalisation see Wagner [9], which contains further results and references on graph-counting polynomials with real zeros.}.  The case of $Q_{(\{1,2\}})$ is similar (real zeros) and will be discussed in Section 6.  The polynomial $Q_{(\{0,1,2\})}$ counts {\it unbranched} subgraphs; the fact that its zeros have negative real part was proved by Ruelle [8].  The other results appear to be new, for instance the fact that the zeros of $Q_{(\{0,1\}\to\{0,2\})}$ (which counts {\it bifurcating} subgraphs) are purely imaginary.
\medskip
	Our method of study of the polynomials $Q_{\cal A}$ uses the Asano contraction (see [1], [6]) and Grace's theorem (see below).  We are thus close to the ideas used in equilibrium statistical mechanics to study the zeros of the grand partition function, in particular the circle theorem of Lee and Yang ([4], [7], and references quoted there).  The machinery of proof of the present paper is developed in Sections 2 to 5.  In Section 6 we deal with the polynomials $Q_{(\{\ldots\})}$ and in Section 7 with the polynomials $Q_{(\{\ldots\}\to\{\ldots\})}$.  Finally, Section 8 discusses the easy extension to (possibly infinite) graphs with weights.
\medskip 
	{\bf 2. Polynomials and their zeros.}
\medskip
	{\sl 2.1 Subsets of {\bf C}.}
\medskip
	We define closed subsets of ${\bf C}$ as follows
$$   \Delta=\{z:{\rm Re}z=1\}=\{\rho e^{i\theta}:\rho={1\over\cos\theta}
	\enspace,\enspace\theta\in(-{\pi\over2},{\pi\over2})\}      $$
$$	\hat\Delta=\{z:{\rm Re}z\ge1\}=\{\rho e^{i\theta}:\rho\ge
{1\over\cos\theta}\enspace,\enspace\theta\in(-{\pi\over2},{\pi\over2})\}     $$
$$	{\cal H}=\{\rho e^{i\theta}:\rho={1\over\sqrt{\cos2\theta}}
	\enspace,\enspace\theta\in(-{\pi\over4},{\pi\over4})\}      $$
$$	\hat{\cal H}=\{\rho e^{i\theta}:\rho\ge{1\over\sqrt{\cos2\theta}}
	\enspace,\enspace\theta\in(-{\pi\over4},{\pi\over4})\}       $$
$$	{\cal P}=\{z=x+iy:1-x={y^2\over4}\}=\{\rho e^{i\theta}:\rho
	={2\over1+\cos\theta}\enspace,\enspace\theta\in(-\pi,\pi)\}      $$
$$	\hat{\cal P}=\{z=x+iy:1-x\ge{y^2\over4}\}=\{\rho e^{i\theta}:\rho
	\ge{2\over1+\cos\theta}\enspace,\enspace\theta\in(-\pi,\pi)\}      $$
Note that ${\cal H}$ is the branch of the hyperbola $\{z=x+iy:x^2-y^2=1\}$ in $\{z=x+iy:x>0\}$; ${\cal P}$ is a parabola with focus at 0.
\medskip
	{\sl 2.2 Symmetric polynomials.}
\medskip
	We shall use symmetric polynomials $p_\sigma$ of the form
$$	p_\sigma(z_1,\ldots,z_n)=a_0+a_1\sum_jz_j+a_2\sum_{j<k}z_jz_k
	+a_3\sum_{j<k<l}z_jz_kz_l+\ldots     $$
where $\sigma$ is a set of integers $\ge0$, and $a_j=1$ for $j\in\sigma$, $a_j=0$ for $j\notin\sigma$.  We consider the cases $\sigma=\{0,1\}$, $\{1,2\}$, $\{0,1,2\}$, $\{0,2\}$, $\{0,2,4\}$, $\{{\rm even}\}$, $\{<{\rm max}\}$, $\{\ge1\}$ as in Section 1, but other choices might be interesting\footnote{*}{Possibly interesting choices are $\{1,3\}$, $\{{\rm odd}\}$.  The choices $\{1\}$, $\{2\}$, $\{{\rm all}\}$ however are not useful for our intended applications.}.  We use the same symbol $p_\sigma$ independently of the number of variables of the polynomial.  This is a mild abuse of notation in the case of $p_{\{<{\rm max}\}}$ (because $\{<{\rm max}\}=\{0,1,\ldots,n-1\}$ depends on the number $n$ of variables).
\medskip
	{\sl 2.3 Proposition.}
\medskip
	{\sl To a symmetric polynomial $p_\sigma$ as above, with $a_0\ne0$, we may associate a closed set $G\subset{\bf C}$ such that $G\not\ni0$ and $p(z_1,\ldots,z_n)\ne0$ if 
$z_1,\ldots,z_n\notin G$, as follows:
\medskip
	(a) $p_{\{0,1\}}(z_1,\ldots,z_n)=1+\sum_{j=1}^nz_j$; $G=-n^{-1}e^{-i\theta}\cos\theta\hat\Delta$ for any $\theta\in(-\pi/2,\pi/2)$.
\medskip
	(b) $p_{\{0,1,2\}}(z_1,\ldots,z_n)=1+\sum_{j=1}^nz_j+\sum_{j<k}z_jz_k$, with $n\ge2$; $G$ is any closed region $\not\ni0$,bounded by a circle or straight line, and containing $\zeta_\pm={-n\pm\sqrt{2n-n^2}\over n(n-1)}$ and $\infty$ (we call $X$ the intersection of all these $G$ and note that ${\bf R}\backslash X=(-2/n,\infty)$), in particular we may take 
$$  G=-{1\over n-1}\sqrt{{2\over n}}e^{-i\theta}\sqrt{\cos2\theta}\,\hat\Delta
\qquad{\rm for}\enspace{\rm any}\qquad\theta\in(-{\pi\over4},{\pi\over4})  $$
\medskip
	(c) We lump together several cases:
$$	p_{\{0,2\}}(z_1,\ldots,z_n)=1+\sum_{j<k}z_jz_k\eqno{(c1)}      $$
$$	p_{\{0,2,4\}}(z_1,\ldots,z_n)=1+\sum_{j<k}z_jz_k
	+\sum_{j<k<l<m}z_jz_kz_lz_m\eqno{(c2)}      $$
$$	p_{\{{\rm even}\}}(z_1,\ldots,z_n)
={1\over2}[\prod_{j=1}^n(1+z_j)+\prod_{j=1}^n(1-z_j)]\eqno{(c3)}      $$
$G=C\hat\Gamma$ where $\hat\Gamma=\Gamma\cup${\rm (outside of $\Gamma$)}, $\Gamma$ is any circle of finite radius through $\pm i$ and $C>0$ is given by $C=\sqrt{2\over n(n-1)}$ (c1), or $C$ is the smallest positive root of $1-{n(n-1)\over2}C^2+{n(n-1)(n-2)(n-3)\over2.3.4}C^4=0$ (c2), or $C=\tan{\pi\over2n}$ (c3).
\medskip
	(d) $p_{\{<{\rm max}\}}(z_1,\ldots,z_n)=\prod_{j=1}^n(1+z_j)-\prod_{j=1}^nz_j$; $G=-{1\over2}\hat\Delta$.
\medskip
	Interesting limiting cases, where $a_0=0$, are the following
\medskip
	(a') $p_{\{1,2\}}(z_1,\ldots,z_n)=\sum_{j=1}^nz_j+\sum_{j<k}z_jz_k$ (consider $p_{\{1,2\}}+\delta$, with $0<\delta\to0$, and take $G=-\delta\,n^{-1}e^{-i\theta}\cos\theta\hat\Delta$ for any $\theta\in(-\pi/2,\pi/2)$; note that this is similar to (a)).
\medskip
	(d') $p_{\{{\ge1}\}}(z_1,\ldots,z_n)=\prod_{j=1}^n(1+z_j)-1$ (consider $p_{\{{\ge1}\}}+1-(1-\delta)^n$, with $0<\delta\to0$, and take $G=\{z:|z+1|\le1-\delta\}$.}
\medskip
	The proposition results from Lemma 2.4 below (don't forget the zeros at infinity).  For (a) we use the fact that the closed half planes through $-1/n$ not containing 0 are of the form
$$	\{z:{\rm Re}(e^{i\theta}(z+n^{-1}))\le0\}
	=-n^{-1}e^{-i\theta}\cos\theta\,\hat\Delta      $$
with $-\pi/2<\theta<\pi/2$.  For (b) notice that the circle through 0, $\zeta_\pm$ has diameter $[-2/n,0]$, from which one gets ${\bf R}\backslash X=(-2/n,+\infty)$.  Also, the left-hand branch $-{1\over n-1}\sqrt{2\over n}\,{\cal H}$ of the hyperbola $\{z=x+iy:x^2-y^2=2/n(n-1)^2\}$ goes through $\zeta_\pm$ and since ${\cal H}$ has tangents $\{z:{\rm Re}(z-e^{i\theta}/\sqrt{\cos2\theta})e^{i\theta}=0\}=e^{-i\theta}\sqrt{\cos2\theta}\,\Delta$, one can take $G$ as stated.  We obtain (c) by direct calculation of the roots of the relevant polynomials.  For (d) we use the fact that the roots of $(1+z)^n-z^n$ have real part -1/2.  For (a') we note that $nz+{n(n-1)\over2}z^2+\delta=0$ has real roots in $(-\infty,-\delta\,n^{-1})$.  For (d') we use the fact that $((1+z)^n-1)+1-(1-\delta)^n=0$ implies $|1+z|=1-\delta$.\qed
\medskip
  Notice also that for (c3) one can take 
$$	G=\{z:|\arg{1-z\over1+z}|\ge{\pi\over n}\}      $$
as is seen by a simple calculation.
\medskip
	Our study of the roots of $Q_{\cal A}$ uses the following lemmas.
\medskip
	{\sl 2.4 Lemma} (Grace's theorem).
\medskip
	{\sl Let $Q(z)$ be a polynomial of degree $n$ with complex
coefficients and $P(z_1,\ldots,z_n)$ the only polynomial which is
symmetric in its arguments, of degree $1$ in each, and such that
$$	P(z,\ldots,z)=Q(z).     $$
If the $n$ roots of $Q$ are contained in a closed circular region $M$,
and $z_1\notin M,\ldots,z_n\notin M$, then $P(z_1,\ldots,z_n)\ne0)$.}
\medskip
	A closed circular region is a closed subset of ${\bf C}$ bounded by a circle or a straight line.  The coefficients of $z^n$, $z^{n-1}$, \dots in $Q(z)$ are allowed to vanish; we then say that some of the roots of $Q(z)$ are at $\infty$, and we must then take $M$ noncompact.
\medskip 
	See Polya and Szeg\"o [5] V, Exercise 145.\qed
\medskip
	{\sl 2.5 Lemma} (Ruelle).
\medskip
	{\sl Let $K$, $L$ be closed subsets of the complex plane {\bf
C}, which do not contain $0$.  Suppose that the complex polynomial
$$	\alpha+\beta z_1+\gamma z_2+\delta z_1z_2     $$
can vanish only when $z_1\in K$ or $z_2\in L$.  Then the polynomial obtained by {\rm Asano contraction}, namely
$$	\alpha+\delta z     $$
can vanish only when $z\in-K*L$, where we have written $K*L=\{z'z'':z'\in K, z''\in L\}$.}
\medskip
	For a proof see [6].\qed
\medskip
	{\sl 2.6 Lemma.}
\medskip
	{\sl Let the coefficients of the polynomials $Q_\lambda(z)$ of order $\le N$ tend to the coefficients of $Q(z)$ when $\lambda\to0$.  If the roots of $Q_\lambda$ are in the closed set $K\subset{\bf C}$ and if $Q$ does not vanish identically, then the roots of $Q$ are in $K$.}
\medskip
	(Roots at infinity are ignored here, only finite roots are considered).  If $Z\notin K$, we may choose $\epsilon>0$ such that $\{z:|z-Z|\le\epsilon\}\cap K=\emptyset$ and $Q(z)\ne0$ if $|z-Z|=\epsilon$.  Since $Q_\lambda$ tends to $Q$ uniformly on the circle $\{z:|z-Z|=\epsilon\}$, the number of zeros of $Q_\lambda$ and $Q$ inside this circle is the same for small $\lambda$, hence $Q(Z)$ does not vanish.\qed
\medskip
	{\bf 3. Graphs.}
\medskip
	Let a finite graph be defined by the vertex set $V$, the edge
set $E$, and the incidence set $I\subset V\times E$ such that  $(j,a)\in
I$ when $j$ is an endpoint of $a$.  [We assume that every vertex is an 
endpoint of at least one edge, that the two endpoints of each edge are
distinct, but we allow several edges between the same endpoints.]  We denote 
by $I(j)$ the set of all $(j,a)\in I$, with fixed $j$.
\medskip
	{\sl 3.1 Proposition.}
\medskip
	{\sl With the above notation, consider the product
$$	\prod_{j\in V}p_\sigma((z_{aj})_{(j,a)\in I(j)})\eqno{(3.1)}      $$
which is a polynomial in the variables $(z_{aj})_{(j,a)\in I}$, linear in each.  If for each monomial of this product we replace each factor $z_{aj}z_{ak}$ (where $j$, $k$ are the endpoints of $a$) by $z_a$, and unmatched $z_{aj}$, $z_{ak}$ by 0, we obtain 
$$   P_{(\sigma)}((z_a)_{a\in E})=\sum_{F\in(\sigma)}\prod_{a\in F}z_a   $$} 
\medskip
	Each monomial of $P_{(\sigma)}$ is of the form $\prod_{a\in F}z_a$, where $F\subset E$.  By construction, the subgraphs $F$ which occur are precisely those for which
$$  (\forall j)\, {\rm card}\{a\in F:j\hbox{ is an endpoint of }a\}\in\sigma $$
This proves the proposition.\qed
\medskip
	If the graph $(V,E)$ is oriented, the incidence set $I$ is the disjoint union of $I'$, $I''$ where $(j,a)\in I'$, $(k,a)\in I''$ mean that the edge $a$ is outgoing at $j$ and ingoing at $k$.  Let us write
$$	I'(j)=I'\cap I(j)\qquad,\qquad I''(j)=I''\cap I(j)      $$
\par
	{\sl 3.2 Proposition.}
\medskip
	{\sl With the above notation, consider the product
$$	\prod_{j\in V}[p_{\sigma'}((z_{aj})_{(j,a)\in I'(j)})
	p_{\sigma''}((z_{bj})_{(j,b)\in I''(j)})]      $$
$$	=\prod_{j\in V}p_{\sigma'}((z_{aj})_{(j,a)\in I'(j)}).
	\prod_{k\in V}p_{\sigma''}((z_{ak})_{(k,a)\in I''(k)})\eqno{(3.2)}    $$
which is a polynomial in the variables $(z_{aj})_{(j,a)\in I}$, linear in each.  If for each monomial in this product we replace each factor $z_{aj}z_{ak}$ (where $j$, $k$ are the endpoints of a) by $z_a$, and unmatched $z_{aj}$, $z_{ak}$ by 0, we obtain 
$$	P_{(\sigma'\to\sigma'')}((z_a)_{a\in E})=
	\sum_{F\in(\sigma'\to\sigma'')}\prod_{a\in F}z_a      $$}
\medskip
	Each monomial of $P_{(\sigma'\to\sigma'')}$ is of the form $\prod_{a\in F}z_a$, where $F\subset E$.  By construction, the subgraphs $F$ which occur are precisely those for which
$$  (\forall j)\,{\rm card}\{\hbox{outgoing edges of $F$ at $j$}\}\in\sigma' $$
$$  (\forall k)\,{\rm card}\{\hbox{ingoing edges of $F$ at $k$}\}\in\sigma'' $$
This proves the proposition.\qed
\medskip
	Propositions 3.1 and 3.2 express that the polynomials $Q_{\cal A}$ introduced in Section 1 can be obtained from a product (3.1) or (3.2) of polynomials $p_\sigma$ by repeated Asano contractions $z_{aj}$, $z_{ak}\to z_a$ (as described in Lemma 2.5), yielding $P_{\cal A}((z_a)_{a\in E})$, then taking 
$$	Q_{\cal A}(z)=P_{\cal A}(z,\ldots,z)      $$
One could in a similar way deal with more general situations than ${\cal A}=({\sigma})$ or ${\cal A}=(\sigma'\to\sigma'')$.
\medskip
	{\bf 4. Geometric results.}
\medskip
	We collect here some facts involving $\Delta$, $\hat\Delta$, ${\cal H}$, $\hat{\cal H}$, and ${\cal P}$, $\hat{\cal P}$ as defined in Section 2.1.  Because $-\log\cos\theta$ is convex on $(-\pi/2,\pi/2)$ we have
$$	{\cal H}*{\cal H}=\hat{\cal H}*\hat{\cal H}=\hat\Delta\eqno{(4.1)}   $$
$$	\Delta*\Delta=\hat\Delta*\hat\Delta=\hat{\cal P}\eqno{(4.2)}      $$
(We shall not use (4.1)).  Since $e^{-i\theta}\cos\theta\,\Delta$ is, for $\theta\in(-\pi/2,\pi/2)$, any line through +1 except the real axis, and $e^{-i\theta}\cos\theta\,\hat\Delta$ is the corresponding closed half plane not containing 0, we have 
$$  \cap_\theta e^{-i\theta}\cos\theta\,\hat\Delta=[1,+\infty)\eqno{(4.3)}   $$
Using (4.2) and simple geometry, it is also clear that 
$$	\cap_\theta(e^{-i\theta}\cos\theta\,\hat\Delta)*
(e^{-i\theta}\cos\theta\,\hat\Delta)=\cap_\theta e^{-2i\theta}\cos^2\theta\,
	\hat{\cal P}=[1,+\infty)\eqno{(4.4)}      $$
\par	
	{\sl 4.1 Proposition.}
\medskip
	{\sl Let $G=\{re^{i\alpha}:r\ge\rho(\alpha)\}$ where $\rho(\cdot)$ is smooth, defined on ${\bf R}({\rm mod}\enspace2\pi)$, or on a closed interval of ${\bf R}({\rm mod}\enspace2\pi)$, or an open interval such that $\rho(\alpha)\to\infty$ when $\alpha$ tends to the endpoints of the interval.  We assume that $\rho(\cdot)>0$, and $\rho(\cdot)+\rho''(\cdot)>0$.  (The limit case $\rho(\alpha)+\rho''(\alpha)=0$ arises when the osculating cercle to the curve $\alpha\mapsto\rho(\alpha)e^{i\alpha}$ passes through 0).  Then
$$  \cap_{\theta\in(-\pi/2,\pi/2)}e^{-i\theta}\cos\theta\,\hat\Delta*G=G  $$}
\medskip
	Note that $G$ is closed $\not\ni0$, and that ${\bf C}\backslash\hat\Delta*G$ is the open convex region around 0 bounded by the envelope $E$ of the lines 
$$	t\mapsto(1+it)\rho(\alpha)e^{i\alpha}      $$
parametrized by $\alpha$.  Expressing that the two {\it real} linear equations 
$$	idt\,\rho(\alpha)e^{i\alpha}
	+(1+it)(i\rho(\alpha)+\rho'(\alpha))e^{i\alpha}\,d\alpha=0      $$
or
$$	i\,dt+(1+it)(i+{\rho'(\alpha)\over\rho(\alpha)})\,d\alpha=0      $$
have a vanishing determinant yields
$$	\left|\matrix{0&\rho'(\alpha)/\rho(\alpha)-t\cr
	1&1+t\rho'(\alpha)/\rho(\alpha)\cr}\right|=0      $$
{\it i.e.}, $t=\rho'(\alpha)/\rho(\alpha)$.  The envelope $E$ is thus given parametrically by the map $\alpha\mapsto E(\alpha)=(\rho(\alpha)+i\rho'(\alpha))e^{i\alpha}$ with derivative $E'(\alpha)=i(\rho(\alpha)+\rho''(\alpha))e^{i\alpha}\ne0$.  In particular $\rho(\cdot)+\rho''(\cdot)>0$ implies that $E(\beta)-E(\alpha)\ne0$ if $0<\beta-\alpha\le\pi$, {\it i.e.}, $E$ has no self-intersection.
\medskip
	The tangent to $E$ at $E(\alpha)$ passes through the point $\rho(\alpha)e^{i\alpha}$ and is orthogonal to the vector $\rho(\alpha)e^{i\alpha}$.  In other words, the orthogonal projection on $\{re^{i\alpha}:r>0\}$ of $({\bf C}\backslash\hat\Delta*G)\cap\{z:|\arg z-\alpha|<\pi/2\}$ is $\{re^{i\alpha}:r>0\}\cap({\bf C}\backslash G)$.  Therefore 
$$	\cup_{\theta\in(-\pi/2,\pi/2)}e^{-i\theta}
	\cos\theta({\bf C}\backslash\hat\Delta*G)={\bf C}\backslash G      $$
or
$$	\cap_{\theta\in(-\pi/2,\pi/2)}e^{-i\theta}\cos\theta\,\hat\Delta*G=G     $$
as announced.\qed
\medskip
	{\sl 4.2 Applications.}
\medskip
	Proposition 4.1 applies to $G=\hat\Delta$, $\hat{\cal H}$.  If $\Gamma$ is a circle containing 0 in its inside, the proposition also applies to $G=\Gamma\cup$(outside of $\Gamma$).  If $\Gamma$ is a circle which does not contain 0 in its inside, and $G=\Gamma\cup$(inside of $\Gamma$), the proposition applies to $[1,+\infty)*G$:
$$	\cap_{\theta\in(-\pi/2,\pi/2)}e^{-i\theta}\cos\theta\,\hat\Delta*G
	=[1,+\infty)*G      $$
\medskip
	{\sl 4.3 Proposition.}
\medskip
	{\sl Let the family $(\Gamma)$ consist of the circles (of finite radius) through $\pm i$, and $\hat\Gamma=\Gamma\cup${\rm (outside of $\Gamma$)}.  Then
$$	\cap\hat\Delta*\hat\Gamma=\{z=x+iy:|y|\ge1\}      $$}
\par
	Taking $\Gamma=\{A+Re^{i\theta}:\theta\in(-\pi,\pi]\}$ with $A$ real, $|A|<R$, we find (as in the proof of Proposition 4.1) that ${\bf C}\backslash\hat\Delta*\hat\Gamma$ is the region inside the envelope $E$ of the lines
$$	t\mapsto(1+it)(A+Re^{i\theta})      $$
parametrized by $\theta$.  Direct calculation shows that $E$ is the ellipse
$$ E=\{z=x+iy:\big({x-A\over R}\big)^2+\big({y\over\sqrt{R^2-A^2}}\big)^2=1\}$$
Here $\sqrt{R^2-A^2}=1$, and the union of the insides of the allowed ellipses is $\{z=x+iy:|y|<1\}$, proving the proposition.\qed
\medskip
	{\bf 5. Calculations of $-G'*G''$.}
\medskip
	Each Asano contraction $z_{aj}$, $z_{ak}\to z_a$ which occurs in Proposition 3.1 or 3.2 involves a variable $z_{aj}$ of a polynomial $p'(n'\hbox{ variables})$ and a variable $z_{ak}$ of a polynomial $p''(n''\hbox{ variables})$.  If $G'$, $G''$ are closed sets associated with $p'$, $p''$ in accordance with Proposition 2.3, we are led by Lemma 2.5 to computing $-G'*G''$ (and then taking an intersection over the possible choices of $G'$ and $G''$).  We proceed by examining various possible cases, without striving for optimal results.

\medskip
	{\sl Case (a)-(a).}
\medskip
	We have $G'=-n'^{-1}e^{-i\theta'}\cos\theta'\hat\Delta$, $G''=-n''^{-1}e^{-i\theta''}\cos\theta''\hat\Delta$, where we allow $\theta'$, $\theta''\in(-\pi/2,\pi/2)$.  Therefore, using Proposition 4.1 and then (4.3),
$$	\cap-G'*G''=-(n'n'')^{-1}\cap_{\theta'\theta''}(e^{-i\theta'}
	\cos\theta'\hat\Delta)*(e^{-i\theta''}\cos\theta''\hat\Delta)      $$
$$	=-(n'n'')^{-1}\cap e^{-i\theta''}\cos\theta''\hat\Delta
	=-(n'n'')^{-1}[1,\infty)=(-\infty,-(n'n'')^{-1}]      $$
if $\theta'$, $\theta''$ are allowed to vary independently.  If we impose $\theta'=\theta''$ the same result is obtained since, using (4.4),
$$	\cap-G'*G''=-(n'n'')^{-1}\cap e^{-2i\theta}\cos^2\theta
\hat\Delta*\hat\Delta=-(n'n'')^{-1}[1,+\infty)=(-\infty,-(n'n'')^{-1}]      $$
\medskip
	{\sl Case (a)-(-).}
\medskip
	Here $G'=-n'^{-1}e^{-i\theta'}\cos\theta'\hat\Delta$ with $\theta'\in(-\pi/2,\pi/2)$.  In our applications, the $G''$ or $[1,\infty)*G''$ satisfy the conditions of Proposition 4.1, and we have thus
$$	\cap-G'*G''=n'^{-1}\cap_{G''}([1,+\infty)*G'')      $$
\par
	{\sl Example.}
\medskip
	Suppose that we may take $G''=C\hat\Gamma$ for all the circles $\Gamma$ (of finite radius) through $\pm i$.  This situation occurs in case (c) of Proposition 2.3, and we have then
$$	\cap[1,+\infty)*G''=\cap G''=iC((-\infty,-1]\cup[1,+\infty))      $$
so that $\cap-G'*G''$ is the imaginary axis minus the interval $i\,n'^{-1}[-C,+C]$.
\medskip
	{\sl Case (a')-(a').}
\medskip
	We have $G'=-\delta\,n'^{-1}e^{-i\theta'}\cos\theta'\hat\Delta$ and $G''=-\delta\,n''^{-1}e^{-i\theta''}\cos\theta''\hat\Delta$, with $\theta'$, $\theta''\in(-\pi/2,\pi/2)$ and $0<\delta\to0$.  These are the same expressions as in case $(a)-(a)$, with an extra factor $\delta$.  Therefore
$$	\cap-G'*G''=(-\infty,-\delta^2(n'n'')^{-1}]\subset(-\infty,0]      $$
\medskip
	{\sl Case (a')-(-).}
\medskip
	We have the same expressions for $\cap-G'*G''$ as in case (a)-(-), but with an extra factor $\delta$.  For example in the case (a')-(b) we have
$$	\cap-G'*G''\subset\{z=x+iy:x\le0,|y|\le x\}      $$
In case (a')-(c), we have 
$$	\cap-G'*G''\subset\hbox{imaginary axis}      $$
\medskip
	{\sl Case (b)-(b).}
\medskip
	We may take 
$$	-G'*G''=-{1\over(n'-1)(n''-1)}{2\over\sqrt{n'n''}}e^{-i\theta'}
e^{-i\theta''}\sqrt{\cos2\theta'}\sqrt{\cos2\theta''}\,\hat\Delta*\hat\Delta $$
with $\theta'$, $\theta''\in(-\pi/4,\pi/4)$.  Using Proposition 4.1, we find
$$	\cap e^{-i\theta'}e^{-i\theta''}\sqrt{\cos2\theta'}\sqrt{\cos2\theta''}
	\,\hat\Delta*\hat\Delta\subset\cap_{\phi\in(-\pi/2,\pi/2)}e^{-i\phi}
	\cos\phi\,\hat\Delta*\hat\Delta=\hat\Delta      $$
so that
$$  \cap-G'*G''\subset-{1\over(n'-1)(n''-1)}{2\over\sqrt{n'n''}}\hat\Delta  $$
If $n'=n''=n$, we recover the result of []:
$$	\cap-G'G''=-{2\over n(n-1)^2}\hat\Delta      $$
This result could be somewhat improved, using circular regions for $G'$, $G''$.
\medskip
	{\sl Case (b)-(c).}
\medskip
	We may take $G'=-{1\over n'-1}\sqrt{2\over n'}e^{-i\theta'}\sqrt{\cos2\theta'}\,\hat\Delta$ and $G''=C''\hat\Gamma$ where $\Gamma$ is any circle (of finite radius) through $\pm i$.  Thus, using Proposition 4.3 and the fact that the $e^{i\theta}\sqrt{\cos2\theta}\,\Delta$ are the tangents to ${\cal H}$, we find
$$   \cap-G'*G''={C''\over n'-1}\sqrt{2\over n'}\cap_{\theta'\in(-\pi/4,\pi/4)}
	e^{-i\theta'}\sqrt{\cos2\theta'}\,\cap_\Gamma\hat\Delta*\hat\Gamma  $$
$$	={C''\over n'-1}\sqrt{2\over n'}\cap_{\theta\in(-\pi/4,\pi/4)}
	e^{-i\theta}\sqrt{\cos2\theta}\,\{z=x+iy:|y|\ge1\}      $$
$$	={iC''\over n'-1}\sqrt{2\over n'}\cap_{\theta\in(-\pi/4,\pi/4)}
	e^{-i\theta}\sqrt{\cos2\theta}\,((-\hat\Delta)\cup\hat\Delta)      $$
$$	={iC''\over n'-1}\sqrt{2\over n'}\,((-\hat{\cal H})\cup\hat{\cal H})
	={C''\over n'-1}\sqrt{2\over n'}\,\{z=x+iy:y^2-x^2\ge1\}      $$
This result could be improved using for $G'$ all closed half-planes $\ni\zeta'_\pm$ and $\not\ni0$.
\medskip
	{\sl Case (b)-(d).}
\medskip
	For some $\epsilon>0$ we may take $G'=-\epsilon e^{-i\theta'}\hat\Delta$, any $\theta\in(-\pi/4,\pi/4)$, and $G''=-{1\over2}\hat\Delta$.  Thus, using (4.2), we get
$$	-G'*G''\subset{\bf C}\backslash\{z=\rho e^{i\theta}:
	\rho>0,\theta\in(-{\pi\over4},{\pi\over4})\}  $$
\medskip
	{\sl Case (b)-(d').}
\medskip
	For some $\epsilon>0$ we may take $G'=-\epsilon e^{-i\theta'}\hat\Delta$, any $\theta\in(-\pi/4,\pi/4)$ , and $G''=-\delta\hat\Delta$, $0<\delta\to0$.  Thus
$$	\cap-G'*G''={\bf C}\backslash\{z=\rho e^{i\theta}:
	\rho>0,\theta\in(-{\pi\over4},{\pi\over4})\}  $$
\medskip
	{\sl Case (c)-(c).}
\medskip
	If $G'=C'\hat\Gamma$, $G''=C''\hat\Gamma$ with circles $\Gamma$ (of finite radius) through $\pm i$ varying independently for $G'$, $G''$, one finds
$$	\cap-G'*G''=C'C''\{z:|z|\ge1\}      $$
This result can be only slightly improved when one has
$$	G'=G''=\{z:|\arg{1-z\over1+z}|\ge{\pi\over n}\}      $$
\medskip
	{\sl Case (c)-(d).}
\medskip
	Taking $G'=C'\hat\Gamma$ where $\Gamma$ is any circle (of finite radius) through $\pm i$ and $G''=-{1\over2}\hat\Delta$ we have, using Proposition 4.3,
$$	\cap-G'*G''=-{C'\over2}\,\cap\hat\Gamma*\hat\Delta
	={C'\over2}\,\{z=x+iy:|y|\ge1\}      $$
\medskip
	{\sl Case (d)-(d).}
\medskip
	Taking $G'=G''=-{1\over2}\hat\Delta$ we have, using (4.2),
$$	-G'*G''=-{1\over4}\hat\Delta*\hat\Delta=-{1\over4}\hat{\cal P}      $$
\par
	{\sl Case (d')-(d').}
\medskip
	Taking $G'=G''=\{z:|z+1|\le1-\delta\}$, with $0<\delta\to0$, we have $G'=G''\subset-\{z=\rho e^{i\theta}:\rho\le2\cos\theta,\theta\in(-\pi/2,\pi/2)\}$, hence
$$	-G'*G''=\{z=\rho e^{i\theta}
	:\rho\le2(1-\cos\theta),\theta\in(-\pi,\pi]\}      $$
(This region is bounded by a cardioid).
\medskip
	{\bf 6. Zeros of graph-counting polynomials.}
\medskip
	In this section we consider the polynomial
$$	Q_{\cal A}(z)=\sum_{F\in{\cal A}}z^{{\rm card}F}      $$
with ${\cal A}=(\sigma)$, and make assertions on the location of its zeros for various choices of $\sigma$.  Following Propositions 3.1, 2.3, 2.5 we have to compute sets $-G*G$.  The computations have mostly been done in Section 5, and we can here simply read off the results.  In what follows, $n$ will denote the maximum number of edges with endpoints at any vertex (degree of the graph $E$).
\medskip
	${\cal A}=(\{0,1\})$
\medskip
	Here ${\cal A}$ consists of dimer subgraphs $F$: each vertex is an endpoint of at most one edge of $F$.  All the zeros of $Q_{(\{0,1\})}$ are real (hence $<0$), as first proved by Heilmann and Lieb [3].  Indeed by case (a)-(a) of Section 5 we find that $Q_{(\{0,1\})}(z)$ can vanish only for
$$	z\in(-\infty,-n^{-2}]     $$
\medskip
	${\cal A}=(\{1,2\})$
\medskip
	The subgraphs $F$ occurring in $(\{1,2\})$ are those unbranched subgraphs which fill $E$.  Here all the zeros are real $\le0$.  Indeed, by case (a')-(a') of Section 5 and Lemma 2.6 we see that $Q_{(\{1,2\})}(z)$ can vanish only for 
$$	z\in(-\infty,0]     $$
\medskip
	${\cal A}=(\{0,1,2\})$
\medskip
	Here ${\cal A}$ consists of the unbranched subgraphs $F$ of $E$ and the zeros of $Q_{\cal A}=Q_{(\{0,1,2\})}$ have negative real part (Ruelle [8]).  Indeed by case (b)-(b) of Section 5, $Q_{(\{0,1,2\})}$ can vanish only if ${\rm Re}z\le-2/n(n-1)^2$, where we have assumed $n\ge2$.
\medskip
	${\cal A}=(\{{\rm even}\})$
\medskip
	Let $E$ be a piece of square lattice in the plane, and ${\cal A}$ consist of those subgraphs $F$ such that each vertex $j\in V$ is an endpoint of exactly 0, 2, or 4 edges $\in F$ (boundary subgraphs).  Fisher [2] has presented evidence that in the limit where $E$ is large (as a piece of square lattice), the zeros of $Q_{\cal A}$ lie asymptotically on the two circles
$$	\{z:|z\pm1|=\sqrt2\}      $$
This conjecture of Fisher, together with the results presented here, raises the hope that the zeros of graph-counting polynomials tend to be localized on curves under fairly general circumstances. 
\medskip
	${\cal A}=(\{<{\rm max}\})$
\medskip
	For each vertex $j\in V$, the subgraphs $F$ which occur in $(\{<{\rm max}\})$ have strictly less edges with endpoint $j$ than $E$ has.  By case (d)-(d) of Section 5, $Q_{(\{<{\rm max}\})}(z)$ can vanish only for $z\in-{1\over4}\hat P$.
\medskip
	${\cal A}=(\{\ge1\})$
\medskip
	The zeros of $Q_{(\{\ge1\})}$ are the inverses of those of $Q_{(\{<{\rm max}\})}$ and therefore lie in 
$$	-\{z=\rho e^{i\theta}:\rho\le2(1+\cos\theta),\theta\in(-\pi,\pi)\}    $$
{\it i.e.}, in a region bounded by a {\it cardioid}.  This also follows from case (d')-(d') of Section 5.
\medskip
	{\bf 7. Oriented graphs.}
\medskip
	Interesting families of subgraphs can be defined when $(V,E)$ is oriented.  Remember that the incidence set $I$ is the disjoint union of $I'$, $I''$, where $(j,a)\in I'$, $(k,a)\in I''$ mean that the edge $a$ begins at $j$ and ends at $k$.  We define
$$	n'=\max_j{\rm card}\{a\in E:(j,a)\in I'\}      $$
$$	n''=\max_k{\rm card}\{a\in E:(k,a)\in I''\}      $$
\par
	We are here concerned with families ${\cal A}=(\sigma'\to\sigma'')$ of subgraphs such that the number of edges of $F$ originating at a vertex and the number of edges ending at a vertex take restricted sets of values $\sigma'$ and $\sigma''$.  The following proposition gives a variety of results on the location of zeros of polynomials of the form $Q_{(\sigma'\to\sigma'')}$, without exhausting possibilities, or giving necessarily best possible results (for improvements the reader is referred to the easy proofs in Section 5).
\medskip
	{\sl 7.1 Proposition.}
\medskip
	{\sl Let again
$$	Q_{\cal A}(z)=\sum_{F\in{\cal A}}z^{{\rm card}F}      $$
We shall write $C'$, $C''$ for the quantity obtained by the replacement $n\to n'$, $n''$ in the definition of $C$ in Proposition 2.3(c).
Then
\medskip
	$Q_{(\{0,1\}\to\{0,1\})}$ has real zeros, located on $(-\infty,-(n'n'')^{-1}]$.  Also $Q_{(\{1,2\}\to\{1,2\})}$ has real zeros, located on $(-\infty,0]$.
\medskip
	$Q_{(\{0,1\}\to\{0,1,2\})}$ has zeros with real part $\le-1/n'(n''-1)$ (we assume $n''\ge2$).  More precisely, the zeros are in $n'^{-1}X''$, where $X''$ is obtained by the replacement $n\to n''$ in the definition of $X$ in Proposition 2.3(b), real zeros are thus $\le-2/n'n''$.  In particular $Q_{(\{0,1\}\to\{0,1,2\})}$ has its zeros in $\{z=x+iy:x<0,|y|<|x|\}$.  Also $Q_{(\{1,2\}\to\{0,1,2\})}$ has its zeros in $\{z=x+iy:x\le0,|y|\le|x|\}$.

\medskip
	$Q_{(\{0,1\}\to\{0,2\})}$, $Q_{(\{0,1\}\to\{0,2,4\})}$, $Q_{\{(0,1\}\to\{{\rm even}\})}$ have purely imaginary zeros, located on $\{z=iy:y^2\ge n'^{-2}C''^2\}$.  Also $Q_{(\{1,2\}\to\{0,2\})}$, $Q_{(\{1,2\}\to\{0,2,4\})}$, $Q_{\{1,2\}\to\{{\rm even}\})}$ have purely imaginary zeros.
\medskip
	$Q_{(\{0,1\}\to\{<{\rm max}\})}$ has zeros with real part $\le-n'^{-1}/2$.  Also $Q_{(\{1,2\}\to\{<{\rm max}\})}$,\hfill\break$Q_{(\{1,2\}\to\{\ge1\})}$ have zeros with real part $\le0$.
\medskip
	$Q_{(\{0,1,2\}\to\{0,1,2\})}$ has zeros with real part $\le-{1\over(n'-1)(n''-1)}{2\over\sqrt{n'n''}}$.
\medskip
	$Q_{(\{0,1,2\}\to\{0,2\})}$, $Q_{(\{0,1,2\}\to\{0,2,4\})}$, $Q_{(\{0,1,2\}\to\{{\rm even}\})}$ have no real zeros; these polynomials are of the form $F(z^2)$ where the zeros of $F$ have real part $\le-{2C''^2\over n'(n'-1)^2}$.
\medskip
	$Q_{(\{0,1,2\}\to\{<{\rm max}\})}$ has its zeros in ${\bf C}\backslash\{z=\rho e^{i\theta}:\rho\ge0,\theta\in[-{\pi\over4},{\pi\over4}]\}$;  $Q_{(\{0,1,2\}\to\{\ge1\})}$  has its zeros in ${\bf C}\backslash\{z=\rho e^{i\theta}:\rho>0,\theta\in(-{\pi\over4},{\pi\over4})\}$
\medskip
	$Q_{(\{0,2\}\to\{<{\rm max}\})}$, $Q_{(\{0,2,4\}\to\{<{\rm max}\})}$, $Q_{(\{{\rm even}\}\to\{<{\rm max}\})}$ have their zeros in $\{z=x+iy:|y|>C'/2\}$, these zeros are thus never real.
\medskip
	$Q_{(\{<{\rm max}\}\to\{<{\rm max}\})}$ has its zeros in $\{z=x+iy:1+4x\ge4y^2\}$.
\medskip
	$Q_{(\{\ge1\}\to\{\ge1\})}$ has its zeros in the region $-\{z=\rho e^{i\theta}:\rho\le2(1+\cos\theta),\theta\in(-\pi,\pi)\}$ (bounded by a cardioid).
\medskip
	Reversing the direction of the arrows produces more polynomials for which one has information on the location of the zeros.}
\medskip
The proposition results from the calculations of Section 5.\qed
\medskip
	We have omitted some trivial cases from the discussion.  Note for instance that $Q_{(\{0,1\}\to\{\ge1\})}={\rm const.}\,z^{{\rm card}V}$, which can vanish only at $z=0$.
\medskip
	{\bf 8. Graphs with weights and infinite graphs.}
\medskip
	Suppose that a weight $W_a>0$ is given to each $a\in E$ and replace $Q_{\cal A}(z)$ by the weighted polynomial
$$  Q_{\cal A}^W(z)=\sum_{F\in{\cal A}}(\prod_{a\in F}W_a)z^{{\rm card}F}  $$
We note that $Q_{\cal A}^W(z)$ is obtained from $P_{\cal A}((z_a)_{a\in E})$ by taking $z_a=W_az$.  In the cases which we considered we had $P_{\cal A}((z_a)_{a\in E})\ne0$ when $z_a\notin\cap-G'*G''$.  We have thus $Q_{\cal A}^W(z)=0$ only when $z\in\cup_{\lambda>0}\lambda\cap-G'*G''$.  This gives a number of easy results as follows:
\medskip
	{\sl 8.1 Proposition.
\medskip
	$Q^W_{(\{0,1\})}$ and $Q^W_{(\{0,1\}\to\{0,1\})}$ have real zeros $<0$; $Q^W_{(\{1,2\})}$ and $Q^W_{(\{1,2\}\to\{1,2\})}$ have real zeros $\le0$.
\medskip
	$Q^W_{(\{0,1,2\})}$, $Q^W_{(\{0,1\}\to\{<{\rm max}\})}$, $Q^W_{(\{0,1,2\}\to\{0,1,2\})}$have zeros with real part $<0$;\hfill\break$Q^W_{(\{1,2\}\to\{<{\rm max}\})}$, $Q^W_{(\{1,2\}\to\{\ge1\})}$ have zeros with real part $\le0$.
\medskip
	$Q^W_{(\{0,1\}\to\{0,2\})}$, $Q^W_{(\{0,1\}\to\{0,2,4\})}$, $Q^W_{(\{0,1\}\to\{{\rm even}\})}$, $Q^W_{(\{1,2\}\to\{0,2\})}$, $Q^W_{(\{1,2\}\to\{0,2,4\})}$,\hfill\break$Q^W_{(\{1,2\}\to\{{\rm even}\})}$ have purely imaginary zeros.
\medskip
	$Q^W_{(\{0,1\}\to\{0,1,2\})}$ has its zeros in $\{z=x+iy:x<0,|y|<|x|\}$; $Q^W_{(\{1,2\}\to\{0,1,2\})}$ has its zeros in $\{z=x+iy:x\le0,|y|\le|x|\}$
\medskip
	$Q^W_{(\{0,1,2\}\to\{0,2\})}$, $Q^W_{(\{0,1,2\}\to\{0,2,4\})}$, $Q^W_{(\{0,1,2\}\to\{{\rm even}\})}$ have their zeros in $\{z=x+iy:|y|>|x|\}$ (they are polynomials of the form $F(z^2)$ where the zeros of $F$ have real part $<0$).
\medskip
	$Q^W_{(\{0,1,2\}\to\{<{\rm max}\})}$ has its zeros in ${\bf C}\backslash\{z=\rho e^{i\theta}:\rho\ge0,\theta\in[-{\pi\over4},{\pi\over4}]\}$;  $Q^W_{(\{0,1,2\}\to\{\ge1\})}$  has its zeros in ${\bf C}\backslash\{z=\rho e^{i\theta}:\rho>0,\theta\in(-{\pi\over4},{\pi\over4})\}$.
\medskip
	$Q^W_{(\{0,2\}\to\{<{\rm max}\})}$, $Q^W_{(\{0,2,4\}\to\{<{\rm max}\})}$, $Q^W_{(\{{\rm even}\}\to\{<{\rm max}\})}$ have no real zeros.
\medskip
	Reversing the direction of the arrows does not change the information given here on the zeros.}
\medskip
	The proofs are the same as for Proposition 7.1.\qed
\medskip
	We have defined a family ${\cal A}=(\ldots)$ (resp.  ${\cal A}=(\ldots\to\ldots)$) of subgraphs $F$ of any finite graph $E$ by restricting the number $\nu$ of allowed edges with a given endpoint (resp. the number $\nu'$ of ingoing edges and $\nu''$ of outgoing edges).  Suppose that 0 is an allowed value of $\nu$ (resp. of $\nu'$ and $\nu''$).  Then we can in a natural manner define the corresponding family ${\cal A}$ of subgraphs of a (countable) infinite graph $E$.  Giving weights $W_a>0$ to the edges $a\in E$, and assuming 
$$	\sum W_a<+\infty      $$
we define 
$$  Q_{\cal A}^W(z)=\sum_{F\in{\cal A}}(\prod_{a\in F}W_a)z^{{\rm card}F}  $$
We have
$$	|Q_{\cal A}^W(z)|\le\prod_{a\in E}(1+W_a|z|)      $$
and therefore $Q_{\cal A}^W$ is an entire analytic function.
\medskip
	Let $V^*$ be a finite subset of the infinite set $V$ of vertices associated with $E$, and $E^*=\{a\in E:$both endpoints of $a$ are $\in V^*\}$.  Also let ${\cal A}(V^*,E^*)$ consist of the subgraphs of $E^*$ which are in ${\cal A}$.  Then
$$  Q^*(z)=\sum_{F\in{\cal A}(V^*,E^*)}(\prod_{a\in F}W_a)z^{{\rm card}F}  $$
satisfies
$$	|Q^*(z)|\le\prod_{a\in E}(1+W_a|z|)       $$
and the coefficients of $Q^*$ tend to those of $Q_{\cal A}^W$ when $V^*$ tends to $E$.  Therefore $Q^*$ tends to $Q_{\cal A}^W$ uniformly on compacts, and the zeros of $Q_{\cal A}^W$ must be limits of zeros of $Q^*$.  This yields the following result.
\medskip
	{\sl 8.2 Proposition.}
\medskip
	{\sl For infinite $E$, the zeros of $Q_{\cal A}^W$ are localized as follows
\medskip
	$Q^W_{(\{0,1\})}$ and $Q^W_{(\{0,1\}\to\{0,1\})}$ have real zeros $<0$.
\medskip
	$Q^W_{(\{0,1,2\})}$, $Q^W_{(\{0,1\}\to\{<{\rm max}\})}$, $Q^W_{(\{0,1,2\}\to\{0,1,2\})}$ have zeros with real part $\le0$.
\medskip
	$Q^W_{(\{0,1\}\to\{0,2\})}$, $Q^W_{(\{0,1\}\to\{0,2,4\})}$, $Q^W_{(\{0,1\}\to\{{\rm even}\})}$ have purely imaginary zeros.
\medskip
	$Q^W_{(\{0,1\}\to\{0,1,2\})}$ has zeros in $\{z=x+iy:x\le0,|y|\le x\}$.
\medskip
	$Q^W_{(\{0,1,2\}\to\{0,2\})}$, $Q^W_{(\{0,1,2\}\to\{0,2,4\})}$, $Q^W_{(\{0,1,2\}\to\{{\rm even}\})}$ have zeros in $\{z=x+iy:|y|\ge|x|\}$ (they are of the form $F(z^2)$ where the zeros of $F$ have real part $\le0$).
\medskip
	$Q^W_{(\{0,1,2\}\to\{<{\rm max}\})}$ has its zeros in ${\bf C}\backslash\{z=\rho e^{i\theta}:\rho>0,\theta\in(-{\pi\over4},{\pi\over4})\}$.
\medskip
	Reversing the direction of the arrows does not change the information given here on the zeros.}
\medskip
	In view of what was said above, this is a direct consequence of Proposition 8.1.\qed
\medskip
	{\bf References.}
	
[1] T. Asano.  ``Theorems on the partition functions of the Heisenberg
ferromagnets.''  J. Phys. Soc. Jap. {\bf 29},350-359(1970).

[2] M.E. Fisher.  ``The nature of critical points'', pp. 1-159 in {\it Lectures in Theoretical Physics} {\bf 7c} Boulder, University of Colorado Press, 1964.

[3] O.J. Heilmann and E.H. Lieb.  ``Theory of monomer-dimer systems.'' 
Commun. Math. Phys. {\bf 25},190-232(1972); {\bf 27},166(1972).

[4] T. D. Lee and C. N. Yang.  ``Statistical theory of equations of state
and phase relations. II.  Lattice gas and Ising model.''  Phys. Rev. {\bf
87},410-419(1952).

[5] G. Polya and G. Szeg\"o.  {\it Aufgaben und Lehrs\"atze aus der
Analysis}, 2 Vol., 3rd ed., Springer, Berlin, 1964.

[6] D. Ruelle.  ``Extension of the Lee-Yang circle theorem.''  Phys. Rev.
Letters {\bf 26},303-304(1971).

[7] D. Ruelle.  ``Some remarks on the location of zeroes of the partition function for lattice systems.''  Commun. Math. Phys. {\bf 31},265-277(1973).

[8] D. Ruelle.  ``Counting unbranched subgraphs.''  J. Algebraic Combinatorics, to appear (archived as mp\_arc 98-104).

[9] D.J. Wagner.  ``Multipartition series''  S.I.A.M. J. Discrete Math.
{\bf 9},529-544(1996).
\end