{
  "id": "1404.2895",
  "version": "v1",
  "published": "2014-04-10T18:20:50.000Z",
  "updated": "2014-04-10T18:20:50.000Z",
  "title": "Coloring sparse hypergraphs",
  "authors": [
    "Jeff Cooper",
    "Dhruv Mubayi"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Fix $k \\geq 3$, and let $G$ be a $k$-uniform hypergraph with maximum degree $\\Delta$. Suppose that for each $l = 2, ..., k-1$, every set of l vertices of G is in at most $\\Delta^{(k-l)/(k-1)}/f$ edges. Then the chromatic number of $G$ is $O( (\\Delta/\\log f)^{1/(k-1)})$. This extends results of Frieze and the second author and Bennett and Bohman. A similar result is proved for 3-uniform hypergraphs where every vertex lies in few triangles. This generalizes a result of Alon, Krivelevich, and Sudakov, who proved the result for graphs. Our main new technical contribution is a deviation inequality for positive random variables with expectation less than 1. This may be of independent interest and have further applications.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-04-10T18:20:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "coloring sparse hypergraphs",
      "second author",
      "chromatic number",
      "extends results",
      "uniform hypergraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.2895C"
    }
  }
}