A note on random greedy coloring of uniform hypergraphs. Issue 3 (30th May 2014) - Cherkashin, Danila D.
Abstract The smallest number of edges forming an n‐uniform hypergraph which is not r‐colorable is denoted by m(n, r). Erdős and Lovász conjectured that m(n, 2)=Θ(n2n). The best known lower bound m(n, 2)=Ω(n/ln(n)2n) was obtained by Radhakrishnan and Srinivasan in 2000. We present a simple proof of their result. The proof is based on the analysis of a random greedy coloring algorithm investigated by Pluhár 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)=Ω((n/ln(n))(r−1)/r rn) 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. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 407–413, 2015