A note on random greedy coloring of uniform hypergraphs. Issue 3 (30th May 2014) - Cherkashin, Danila D.; Kozik, Jakub
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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsnk1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />m(n, 2)=Θ(n2n)</alternatives>. The best known lower bound <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsnrs" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />m(n, 2)=Ω(n/ln(n)2n)</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsnpp" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />m(n, r)=Ω((n/ln(n))(r−1)/r rn)</alternatives> 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