Coloring Hypergraphs from Random Lists
We introduce and study problems on coloring hypergraphs from randomly chosen color lists. Let H=H(n) be an r-uniform hypergraph on n vertices where each vertex is assigned a list of colors of size k chosen independently and uniformly at random from all k-subsets of a set of colors of size σ=σ(n). We prove a number of results concerning the probability of the existence of a list coloring of H from the random lists. One such result is that for fixed r, k and growing n, if σ = ω(n^1k^2(r-1) Δ^1k(r-1) ), and H(n) has maximum degree Δ = O(n^k-1k^2(k^2+k) r(r - 1) ), then with probability tending to 1, as n → ∞, H has a proper coloring from the random lists. The bound on σ is tight. We also prove analogous results for hypergraphs of bounded maximum degree and complete hypergraphs where the size k of the random lists either is constant or an increasing function of n. In particular, for the complete r-uniform hypergraph K_n^r, if σ = n/(r-1) ceil, then the property of being colorable from random lists of size k has a sharp threshold at k(n) = nr-1. , number=4, journal=The Electronic Journal of Combinatorics, author=Casselgren, Carl Johan, year=2024, month=Dec., pages=#P4.75