{
  "id": "1310.1368",
  "version": "v1",
  "published": "2013-10-04T18:40:08.000Z",
  "updated": "2013-10-04T18:40:08.000Z",
  "title": "A note on random greedy coloring of uniform hypergraphs",
  "authors": [
    "Danila D. Cherkashin",
    "Jakub Kozik"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "The smallest number of edges forming an n-uniform hypergraph which is not r-colorable is denoted by m(n,r). Erd\\H{o}s and Lov\\'{a}sz conjectured that m(n,2)=\\theta(n 2^n)$. The best known lower bound m(n,2)=\\Omega(sqrt(n/log(n)) 2^n) was obtained by Radhakrishnan and Srinivasan in 2000. We present a simple proof of their result. The proof is based on analysis of random greedy coloring algorithm investigated by Pluh\\'ar in 2009. The proof method extends to the case of r-coloring, and we show that for any fixed r we have m(n,r)=\\Omega((n/log(n))^(1-1/r) r^n) improving the bound of Kostochka from 2004. We also derive analogous bounds on minimum edge degree of an n-uniform hypergraph that is not r-colorable.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-10-04T18:40:08.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C65",
      "05D40",
      "G.2.1",
      "G.2.2",
      "G.3"
    ],
    "keywords": [
      "uniform hypergraphs",
      "n-uniform hypergraph",
      "proof method extends",
      "random greedy coloring algorithm",
      "minimum edge degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1310.1368C"
    }
  }
}