Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
| dc.creator | Krzakala, Florent | |
| dc.creator | Pagnani, Andrea | |
| dc.creator | Weigt, Martin | |
| dc.date | 2004-03-30 | |
| dc.date | 2004-07-28 | |
| dc.date.accessioned | 2026-07-07T02:57:21Z | |
| dc.date.available | 2026-07-07T02:57:21Z | |
| dc.description | 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. | |
| dc.description | 23 pages, 10 figures. Replaced with accepted version | |
| dc.identifier | https://arxiv.org/abs/cond-mat/0403725 | |
| dc.identifier | http://arxiv.org/abs/cond-mat/0403725 | |
| dc.identifier | Phys. Rev. E 70, 046705 (2004) | |
| dc.identifier | doi:10.1103/PhysRevE.70.046705 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/23633 | |
| dc.subject | Disordered Systems and Neural Networks | |
| dc.subject | Statistical Mechanics | |
| dc.subject | Computational Complexity | |
| dc.title | Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs | |
| dc.type | text |