Choosability of multipartite hypergraphs

A $k$-uniform hypergraph (or $k$-graph) $H=(V,E)$ is $k$-partite if $V$ can be partitioned into $k$ sets $V_1,\dots ,V_k$ such that each edge in $E$ contains precisely one vertex from each $V_i$. We show that $k$-partite $k$-graphs of maximum degree $\mathrm{\Delta }$ are $q$-choosable for $q\ge {(\frac{4}{5}(k-1+o(1))\mathrm{\Delta }\mathrm{/}\log \mathrm{\Delta })}^{1\mathrm{/}(k-1)}$. Our proof yields an efficient randomized algorithm for finding such a coloring, which shows that the conjectured algorithmic barrier for coloring pseudorandom $k$-graphs does not apply to $k$-partite $k$-graphs.