2013/10/04 by Cherkashin, Danila D., Kozik, Jakub · 1 citation
#05C15 #05C65 #05D40 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #G.3
paper · doi:10.48550/arxiv.1310.1368
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)=θ(n 2n). The best known lower bound m(n,2)=Ω(sqrt(n/log(n)) 2n) 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á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/log(n))^(1-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.