Estimating the \(r\)-colorability threshold for a random hypergraph (Q2185741)

This paper studies the chromatic number \(\chi\) of a random hypergraph with edge probability \(p\) over a complete \(n\)-vertex \(k\)-uniform hypergraph denoted by \(H(n,k,p)\). Let \(k\ge 4\) and \(r\ge 3\) (number of colors) be integers and \(c>0\). It is shown that there are constants \(C>0\) and \(d_0>0\) satisfying that if \(\max\{r,k\}>d_0\) and \(c<r^{k-1}\ln r-(\ln r)/2-(r-1)/r-Ck^2(\ln r)/r^{k/3-1}\), then \(\mathbb{P}(\chi(H(n,k,cn/\binom{n}{k}))\le r)\) tends to 1 as \(n\) goes to infinity. The same proof also essentially works for the case \(r=2\) colors.