1. List colourings of multipartite hypergraphs
- Author
-
Méroueh, Arès and Thomason, Andrew
- Subjects
Mathematics - Combinatorics ,05C15 - 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_nd$. 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\ge4$., Comment: Accepted version
- Published
- 2017
- Full Text
- View/download PDF