%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