We study the problem of constructing a (near) uniform random proper q-coloring of a simple k-uniform hypergraph with n vertices and maximum degree Δ. (Proper in that no edge is mono-colored and simple in that two edges have maximum intersection of size one.) We show that if for some α<1 we have Δ≥ nα and q≥Δ ( 1+α)/kα then Glauber dynamics will become close to uniform in O(nlogn) time from a random (improper) start. Note that for k>1+α-1 we can take q=o(Δ).
E-mail addresses: email@example.com (A. Frieze), firstname.lastname@example.org (P. Melsted). 1 Supported in part by NSF grant CCF-0502793.