%This paper has been accepted for publication by the
% JOURNAL OF ALGEBRAIC COMBINATORICS
%
\magnification=1200
\def\qed{\unskip\kern 6pt\penalty 500\raise -2pt\hbox
{\vrule\vbox to 10pt{\hrule width 4pt\vfill\hrule}\vrule}}
\centerline{COUNTING UNBRANCHED SUBGRAPHS.}
\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 an arbitrary
finite graph, the polynomial $Q(z)$ $=\sum_{F\in {\cal U}}z^{{\rm card}F}$
associates a weight $z^{{\rm card}F}$ to each unbranched subgraph $F$ of
length ${\rm card}F$. We show that all the zeros of $Q$ have negative
real part.\par}
\bigskip\bigskip
A graph $(V,E,v)$ consists of a finite set $V$ of vertices, a
finite set $E$ of edges, and a map $v$ of $E$ to the two-element subsets
of $V$. If $a\in E$ and $v(a)=\{j,k\}$, we say that the edge $a$ joins
the vertices $j$, $k$. [We impose that $j\ne k$, but allow different
edges to join the same two vertices. We assume that each vertex $j$ is
in $v(a)$ for some $a\in E$].
\medskip
For our purposes a {\it subgraph} of $(V,E,v)$ will be a graph
$(V,F,\phi)$ where $F\subset E$ and $\phi=v|F$. We shall now fix
$(V,E,v)$, and say that $F$ is a subgraph of $E$ if $F\subset E$ (this
defines $(V,F,\phi)$ uniquely). We define the subset ${\cal U}$ of
{\it unbranched} subgraphs of $E$ by
$$ {\cal U}=\{F\subset E:(\forall j)\,{\rm card}\{a\in F:v(a)\ni j\}\le2\} $$
\par
{\bf 1. Proposition.}
\medskip
{\sl The polynomial
$$ Q_{\cal U}(z)=\sum_{F\in{\cal U}}z^{{\rm card}F} $$
has all its zeros in $\{z:{\rm Re}z\le-2/n(n-1)^2\}$ where $n\ge2$ is the
largest number of edges ending in any vertex $j$.}
\medskip
The proof is given in Section 5 below. This result is related
to a well-known theorem of Heilman and Lieb [2] on counting dimer
subgraphs (for which ${\rm card}\{a\in F:v(a)\ni j\}\le1$).
\medskip
Let us consider an edge $a$ as a closed line segment containing
the endpoints $j,k\in v(a)$. Also identify a subgraph $F\subset E$
with the union of its edges. Then $F$ is the union of its connected
components, and if $F\in{\cal U}$, these are homeomorphic to a line
segment or to a circle. We call $b(F)$ the number of components
homeomorphic to a line segment, therefore
$$ 2b(F)={\rm card}\{j\in V:v(a)\ni j
{\rm\enspace for\enspace exactly\enspace one\enspace}a\in F\} $$
Let us define
$$ Q_{\cal U}(z,t)=\sum_{F\in{\cal U}}z^{{\rm card}F}t^{b(F)}. $$
We see that
$$ Q_{\cal U}(z,1)=Q_{\cal U}(z). $$
\par
{\bf 2. Proposition.}
\medskip
{\sl If $t$ is real $\ge2-2/n$, then $Q_{\cal U}(z,t)$ has all
its zeros (with respect to $z$) on the negative real axis.}
\medskip
The proof is given in Section 6 below. For $t\ge2$, this is a
special case a theorem of Wagner [6] as pointed out by the referee (take
$Q_v(y)=1+sy+y^2/2$ for each vertex $v$ in Theorem 3.2 of [6]).
\medskip
We shall use the following two lemmas.
\medskip
{\bf 3. Lemma.}
\medskip
{\sl Let $A$, $B$ 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 A$ or $z_2\in B$. Then
$$ \alpha+\delta z $$
can vanish only when $z\in-AB$.}
\medskip
This is the key step in an extension (see Ruelle [5]) of the
Lee-Yang circle theorem [3]. Note that in applications of the lemma, the
coefficients $\alpha$, $\beta$, $\gamma$, $\delta$ are usually polynomials
in variables $z_j$ (different from $z_1$, $z_2$, $z$).
\medskip
{\bf 4. Lemma.}
\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 roots of $Q$ are all 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
This is Grace's theorem, see Polya and Szeg\"o [4] V, Exercise
145.
\medskip
{\bf 5. Proof of Proposition 1.}
\medskip
If $a\in E$, and $v(a)=\{j,k\}$, we introduce complex variables
$z_{aj}$, $z_{ak}$. For each $j\in V$, let $p_j$ be the polynomial in
$Z^{(j)}=(z_{aj})_{v(a)\ni j}$ such that
$$ p_j(Z^{(j)})=1+\sum_az_{aj}+\sum_{a\ne b}z_{aj}z_{bj} $$
(where we assume $v(a)\ni j$, $v(b)\ni j$). Putting all $z_{aj}$ equal
to $z$, we obtain a polynomial
$$ q_j(z)=1+n_jz+{n_j(n_j-1)\over2}z^2 $$
where $n_j>0$ is the number of edges ending in $j$. Define
$\zeta_{\pm}^{(j)}=-1$ when $n_j=1$ or $2$, and
$$ \zeta_{\pm}^{(j)}={-n_j\pm\sqrt{2n_j-n_j^2}\over n_j(n_j-1)} $$
if $n_j\ge2$. The zeros of $q_j$, considered as a polynomial of degree
$n_j$ are $\zeta_{\pm}^{(j)}$, and $\infty$ if $n_j>2$. They are
therefore contained in the closed circular regions (half-planes)
$$ H_{\theta+}^{(j)}=\{z:{\rm Re}[e^{-i\theta}(z-\zeta_+^{(j)})]\le0\} $$
$$ H_{\theta-}^{(j)}=\{z:{\rm Re}[e^{i\theta}(z-\zeta_-^{(j)})]\le0\} $$
for $0\le\theta<\pi/4$. By Lemma 4, we have thus $p_j(Z^{(j)})\ne0$ if
$z_{aj}\notin H_{\theta\pm}^{(j)}$ for all $a\in E$ such that $j\in v(a)$.
\medskip
If a polynomial is separately of first order in two variables
$z_1$, $z_2$, {\it i.e.}, it is of the form
$$ \alpha+\beta z_1+\gamma z_2+\delta z_1z_2 $$
the {\it Asano contraction} [1] consists in replacing it by the first order
polynomial
$$ \alpha+\delta z $$
in one variable $z$, as in Lemma 3. As already noted, the coefficients
$\alpha$, $\beta$, $\gamma$, $\delta$ may depend on variables $z_i$
different from $z_1$, $z_2$, $z$. Let now $Z=(z_a)_{a\in E}$ and
$$ P_{\cal U}(Z)=\sum_{F\in{\cal U}}\prod_{a\in F}z_a. $$
If we take the product $\prod_{j\in V}p_j(Z^{(j)})$ and perform the
Asano contraction
$$ \alpha+\beta z_{aj}+\gamma z_{ak}+\delta z_{aj}z_{ak}\qquad
\longrightarrow\qquad \alpha+\delta z_a $$
for all $a\in E$ we obtain $P_{\cal U}(Z)$. Using Lemma 3 iteratively,
once for each edge $a\in E$, we see thus that $P_{\cal U}(Z)$ has no
zeros when for each $a\in E$
$$ z_a\in{\bf C}\setminus(-H_{\theta\pm}^{(j)}H_{\theta\pm}^{(k)}) $$
where $v(a)=\{j,k\}$ and
$$ H_{\theta\pm}^{(j)}H_{\theta\pm}^{(k)}
=\{uv:u\in H_{\theta\pm}^{(j)}, v\in H_{\theta\pm}^{(k)}\}. $$
We have
$$ {\bf C}\setminus(-H_{\theta\pm}^{(j)}H_{\theta\pm}^{(k)})
\supset{\bf C}\setminus(-H_{\theta\pm}H_{\theta\pm}) $$
where $H_{\theta\pm}$ is the largest $H_{\theta\pm}^{(j)}$ (obtained by
replacing $n_j$ by $n=\max_jn_j$). Note that ${\bf
C}\setminus(-H_{\theta\pm}H_{\theta\pm})$ is the interior of a parabola
passing through $-\zeta_{\pm}^2$ and with axis passing through $0$ and
making an angle $\pm2\theta$ with the positive real axis. When $\pm\theta$
varies between $-\pi/4$ and $\pi/4$, the parabola sweeps the region
${\rm Re}z>-{\rm Re}\zeta_{\pm}^2=-2/n(n-1)^2$. Since $Q_{\cal U}(z)$
is obtained from $P_{\cal U}(Z)$ by putting all $z_a$ equal to $z$,
this proves Proposition 1.\qed
\medskip
{\bf 6. Proof of Proposition 2.}
\medskip
We proceed as for Proposition 1, defining here
$$ p_j(Z^{(j)})=1+s\sum_az_{aj}+\sum_{a\ne b}z_{aj}z_{bj} $$
$$ q_j(z,t)=1+n_jsz+{n_j(n_j-1)\over2}z^2 $$
If $s\ge\sqrt{2-2/n_j}$, the roots of $q_j$ are real negative, and the
same type of argument used for theorem 1 shows that all the zeros of
$Q_{\cal U}(z,s^2)$ are real and negative.\qed
\medskip
{\bf Acknowledgements.} I am indebted to Jozsef Beck, Jeff
Kahn, and Chris Godsil for their interest and advice, and to an
anonymous referee for useful detailed criticism.
\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] O.J. Heilmann and E.H. Lieb. "Theory of monomer-dimer systems."
Commun. Math. Phys. {\bf 25},190-232(1972); {\bf 27},166(1972).
[3] 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).
[4] G. Polya and G. Szeg\"o. {\it Aufgaben und Lehrs\"atze aus der
Analysis}, 2 Vol., 3rd ed., Springer, Berlin, 1964.
[5] D. Ruelle. "Extension of the Lee-Yang circle theorem." Phys. Rev.
Letters {\bf 26},303-304(1971).
[6] D.J. Wagner. "Multipartition series" S.I.A.M. J. Discrete Math.
{\bf 9},529-544(1996).
\end