Approximating real-rooted and stable polynomials, with combinatorial applications

Abstract

Let $p(x)=a_0+a_{1}x+\dots +a_n{x}^n$ be a polynomial with all roots real and satisfying $x\le -\delta$ for some $0<\delta <1$. We show that for any $0<\epsilon <1$, the value of $p(1)$ is determined within relative error $\epsilon$ by the coefficients $a_k$ with $k\le \frac{c}{\sqrt{\delta }}\ln \frac{n}{\epsilon \sqrt{\delta }}$ for some absolute constant $c>0$. Consequently, if $m_k(G)$ is the number of matchings with $k$ edges in a graph $G$, then for any $0<\epsilon <1$, the total number $M(G)=m_0(G)+m_1(G)+\dots$ of matchings is determined within relative error $\epsilon$ by the numbers $m_k(G)$ with $k\le c\sqrt{\Delta }\ln (v/\epsilon )$, where $\Delta$ is the largest degree of a vertex, $v$ is the number of vertices of $G$ and $c>0$ is an absolute constant. We prove a similar result for polynomials with complex roots satisfying $\Re z\le -\delta$ and apply it to estimate the number of unbranched subgraphs of $G$.

12 pages

Cited by in corpus (1)

• More on zeros and approximation of the Ising partition function