Paper detail

Tight bounds on the threshold for permuted k-colorability

If each edge (u,v) of a graph G=(V,E) is decorated with a permutation pi_{u,v} of k objects, we say that it has a permuted k-coloring if there is a coloring sigma from V to {1,...,k} such that sigma(v) is different from pi_{u,v}(sigma(u)) for all (u,v) in E. Based on arguments from statistical physics, we conjecture that the threshold d_k for permuted k-colorability in random graphs G(n,m=dn/2), where the permutations on the edges are uniformly random, is equal to the threshold for standard graph k-colorability. The additional symmetry provided by random permutations makes it easier to prove bounds on d_k. By applying the second moment method with these additional symmetries, and applying the first moment method to a random variable that depends on the number of available colors at each vertex, we bound the threshold within an additive constant. Specifically, we show that for any constant epsilon > 0, for sufficiently large k we have 2 k ln k - ln k - 2 - epsilon < d_k < 2 k ln k - ln k - 1 + epsilon. In contrast, the best known bounds on d_k for standard k-colorability leave an additive gap of about ln k between the upper and lower bounds.