Randomly coloring simple hypergraphs

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 Delta. (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 alpha < 1 we have Delta >= n(alpha) and q >= Delta((1+alpha)/k alpha) then Glauber dynamics will become close to uniform in O(n log n) time from a random (improper) start. Note that for k > 1 + alpha(-1) we can take q = 0(Delta). (C) 2011 Elsevier B.V. All rights reserved.