Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs

Details Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs

2004-03-30

arxiv.org/abs/cond-mat/0403725v2

Phys. Rev. E 70, 046705 (2004)

Physics

Condensed Matter

Disordered Systems and Neural Networks

23 pages, 10 figures. Replaced with accepted version

Scientific paper

10.1103/PhysRevE.70.046705

We consider the problem of coloring Erdos-Renyi and regular random graphs of finite connectivity using q colors. It has been studied so far using the cavity approach within the so-called one-step replica symmetry breaking (1RSB) ansatz. We derive a general criterion for the validity of this ansatz and, applying it to the ground state, we provide evidence that the 1RSB solution gives exact threshold values c_q for the q-COL/UNCOL phase transition. We also study the asymptotic thresholds for q >> 1 finding c_q = 2qlog(q)-log(q)-1+o(1) in perfect agreement with rigorous mathematical bounds, as well as the nature of excited states, and give a global phase diagram of the problem.

Affiliated with

Also associated with

No associations

Rating

Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs 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 Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-78545