%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