Tight bounds on the threshold for permuted k-colorability

Details Tight bounds on the threshold for permuted k-colorability Tight bounds on the threshold for permuted k-colorability

2011-11-12

arxiv.org/abs/1111.2947v1

Mathematics

Combinatorics

12 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Tight bounds on the threshold for permuted k-colorability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tight bounds on the threshold for permuted k-colorability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tight bounds on the threshold for permuted k-colorability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-3339