Randomly coloring simple hypergraphs with fewer colors

Abstract

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 $q\ge \max \{C_k\log n,500k^3{\Delta }^{1/(k-1)}\}$ then the Glauber Dynamics will become close to uniform in $O(n\log n)$ time, given a random (improper) start. This improves on the results in Frieze and Melsted [5].

arXiv admin note: text overlap with arXiv:0901.3699

References in corpus (1)

• Absence of Phase Transition for Antiferromagnetic Potts Models via the Dobrushin Uniqueness Theorem