On the chromatic numbers of random hypergraphs (Q2243791)

Let \(H(n,k,p)\) denote the random \(k\)-uniform hypergraph on the vertex set \([n]=\{1,2,\ldots, n\}\) where each \(k\)-element subset is retained as a hyperedge with probability \(p\) independent of all other hyperedges. We are interested in the chromatic number \(\chi\) of the hypergraph, namely the smallest number \(s\) such that there is a colouring of the vertices with \(s\) colours in such a way that no hyperedge has all its vertices the same colour. Generalising earlier results of \textit{T. Łuczak} [Combinatorica 11, No. 3, 295--297 (1991; Zbl 0771.05091)] and subsequently others about the concentration of the chromatic number of 2-uniform random hypergraphs (i.e. random graphs), results were shown in [\textit{M. Dyer} et al., J. Comb. Theory, Ser. B 113, 68--122 (2015; Zbl 1315.05051)] about the concentration of the chromatic number of \(H(n,k,p)\) when the expected number of edges \(\binom{n}{k}p\) is a linear function of \(n\). The aim of the paper under review is to extend these results to dense cases where \(\binom{n}{k}p/n \rightarrow \infty\) as \(n\rightarrow \infty\). This is achieved as a consequence of two theorems. The first states that if \(c=c(n)=p\binom{n}{k}/n\) and \(\varepsilon>0\), then if \(c(n)\rightarrow \infty\) as \(n\rightarrow\infty\) but \(c(n)=o(n)\), then for any function \(r(n)\) tending to infinity with \(n\), provided \[c>r^{k-1}\log(r)-\log(r)/2+\varepsilon,\] it is true that, as \(n\rightarrow \infty\), we have \[\mathbb{P}(\chi(H(n,k,p))>r)\rightarrow 1.\] The second, more substantial theorem goes in the opposite direction. Suppose now an integer \(k\geq 4\) and \(\gamma \in (0,1/8)\) are fixed and that \(c(n)\) is defined as in the previous theorem. Suppose now that \(c(n)\) both tends to infinity with \(n\) (as before) but also now satisfies the more demanding upper bound \(c(n)\leq n^{(k-1)\gamma /(2k+4)}\), then there is an absolute constant \(A\) such that whenever \(r(n)\rightarrow\infty\) with \[c < r^{k-1}\log(r)-\frac{\log(r)}{2}-\frac{r-1}{r} -A\left(\frac{k^{2}\log(r)}{r^{k/3-1}}\right)\] it is true that, as \(n\rightarrow\infty\) \[\mathbb{P}(\chi(H(n,k,p))\leq r+1)\rightarrow 1.\] A concentration result on at most three values (and in many intervals two values) follows from these two results. Proofs involve results on an optimisation problem for doubly stochastic matrices to get a lower bound on the probability that \(H(n,k,p)\) has a proper \(r\)-colouring, then using martingale results to properly colour most of the hypergraph and a lemma to show that the remainder has at worst bounded chromatic number.