Approximating real-rooted and stable polynomials, with combinatorial applications

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$,thevalueof$p(1)$isdeterminedwithinrelativeerror$\epsilon$bythecoefficients$a_k$with$k \leq {c \over \sqrt{\delta}} \ln {n \over \epsilon \sqrt{ \delta}}$forsomeabsoluteconstant$c > 0$. Consequently, if $m_k(G)$ is the number of matchings with $k$ edges in a graph $G$, then for any $0<ϵ<1$, the total number $M(G)=m_0(G)+m_1(G) + \ldots $ofmatchingsisdeterminedwithinrelativeerror$\epsilon$ by the numbers $m_k(G)$ with $k\le c\sqrt{\mathrm{\Delta }}\ln (v\mathrm{/}ϵ)$, where $\mathrm{\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 $\mathrm{\Re }z\le -\delta$ and apply it to estimate the number of unbranched subgraphs of $G$.