List colorings of multipartite hypergraphs. Issue 4 (1st April 2019)

• Record Type: Journal Article
• Authors: Méroueh, Arès; Thomason, Andrew
• Is Part Of: Random structures & algorithms. Volume 55:Issue 4(2019)
• Page Start: 950
• Page End: 979
• Publication Date: 2019-04-01
• Subjects: hypergraph -- list colouring; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20848
• Languages: English
• ISSNs: 1042-9832

Abstract

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.