{
  "id": "1209.5185",
  "version": "v4",
  "published": "2012-09-24T08:17:05.000Z",
  "updated": "2015-09-02T04:21:15.000Z",
  "title": "Bounds on Characteristic Polynomials",
  "authors": [
    "Suijie Wang",
    "Yeong-Nan Yeh",
    "Fengwei Zhou"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Suppose $G$ is a simple graph with $n$ vertices, $m$ edges, and rank $r$. Let $\\chi_G(t)=a_0t^n-a_1t^{n-1}+\\cdots +(-1)^ra_rt^{n-r}$ be the chromatic polynomial of $G$. For $q,k\\in \\Bbb{Z}$ and $0\\le k\\le q+r+1$, we obtain a sharp two-side bound for the partial binomial sum of the coefficient sequence, that is, \\[ {r+q\\choose k}\\le \\sum_{i=0}^{k}{q\\choose k-i}a_{i}\\le {m+q\\choose k}. \\] Indeed, this bound holds for the characteristic polynomial of hyperplane arrangements and matroids, and its weak version can be generalized to the characteristic polynomial of toric arrangements and arithmetic matroids. We also propose a problem on the geometric interpretation of the above bound.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2014-02-26T13:33:12.000Z",
      "title": "Bounds on Chromatic Polynomials",
      "abstract": "Let $\\chi_G(t)=a_0t^n-a_1t^{n-1}+\\cdots (-1)^ra_rt^{n-r}$ be the chromatic polynomial of a simple graph $G$. For $q,k\\in \\Bbb{Z}$ and $0\\le k\\le q+r+1$, we obtain a sharp two-side bound for the partial binomial sum of the coefficient sequence, that is, \\[ {r+q\\choose k}\\le \\sum_{i=0}^{k}{q\\choose k-i}a_{i}\\le {m+q\\choose k}. \\]",
      "comment": null,
      "journal": null,
      "doi": null,
      "authors": [
        "Suijie Wang",
        "Yeong-Nan Yeh"
      ]
    },
    {
      "version": "v4",
      "updated": "2015-09-02T04:21:15.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C31"
    ],
    "keywords": [
      "chromatic polynomial",
      "partial binomial sum",
      "sharp two-side bound",
      "coefficient sequence",
      "simple graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1209.5185W"
    }
  }
}