List colourings of multipartite hypergraphs

Abstract

Let ${\chi }_l(G)$ denote the list chromatic number of the $r$-uniform hypergraph~$G$. Extending a result of Alon for graphs, Saxton and the second author used the method of containers to prove that, if $G$ is simple and $d$-regular, then ${\chi }_l(G)\ge (1/(r-1)+o(1)){\log }_{r}d$. To see how close this inequality is to best possible, we examine ${\chi }_l(G)$ when $G$ is a random $r$-partite hypergraph with $n$ vertices in each class. The value when $r=2$ was determined by Alon and Krivelevich, here we show that ${\chi }_l(G)=(g(r,\alpha )+o(1)){\log }_{r}d$ almost surely, where $d$ is the expected average degree of~$G$ and $\alpha ={\log }_{n}d$. The function $g(r,\alpha )$ is defined in terms of "preference orders" and can be determined fairly explicitly. This is enough to show that the container method gives an optimal lower bound on ${\chi }_l(G)$ for $r=2$ and $r=3$, but, perhaps surprisingly, apparently not for $r\ge 4$.

Accepted version

References in corpus (3)

• Hypergraph containers
• Online containers for hypergraphs, with applications to linear equations
• Simple containers for simple hypergraphs