Approximating real-rooted and stable polynomials, with combinatorial applications

Abstract

Let $p(x)=a_0+a_{1}x+\cdots +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<ϵ0$. As a corollary, we show that if $m_k(G)$ is the number of matchings with $k$ edges in a graph $G$, then for any $0<ϵ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$.