\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_{j0$ 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_{j0$ 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|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