List colorings of multipartite hypergraphs. Issue 4 (1st April 2019) - Méroueh, Arès; Thomason, Andrew
Abstract : Let χ 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 χ l ( G ) ≥ ( 1 / ( r − 1 ) + o ( 1 ) ) log r d . To see how close this inequality is to best possible, we examine χ 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 χ l ( G ) = ( g ( r, α ) + o ( 1 ) ) log r d almost surely, where d is the expected average degree of G and α = log n d . The function g ( r, α ) 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 χ l ( G ) for r = 2 and r = 3, but, perhaps surprisingly, apparently not for r ≥ 4.