{
  "id": "1806.07404",
  "version": "v1",
  "published": "2018-06-19T18:01:23.000Z",
  "updated": "2018-06-19T18:01:23.000Z",
  "title": "Approximating real-rooted and stable polynomials, with combinatorial applications",
  "authors": [
    "Alexander Barvinok"
  ],
  "comment": "12 pages",
  "categories": [
    "math.CO",
    "cs.DS",
    "math.CA"
  ],
  "abstract": "Let $p(x)=a_0 + a_1 x + \\ldots + a_n x^n$ be a polynomial with all roots real and satisfying $x \\leq -\\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 \\leq {c \\over \\sqrt{\\delta}} \\ln {n \\over \\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) + \\ldots $ of matchings is determined within relative error $\\epsilon$ by the numbers $m_k(G)$ with $k \\leq 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\\thinspace z \\leq -\\delta$ and apply it to estimate the number of unbranched subgraphs of $G$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-06-19T18:01:23.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "26C10",
      "30C15",
      "05A16",
      "05C30",
      "05C31"
    ],
    "keywords": [
      "combinatorial applications",
      "stable polynomials",
      "absolute constant",
      "relative error",
      "complex roots"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}