How Many Colors to Color a Random Graph? Cavity, Complexity, Stability and All That

スポンサーリンク

概要

• 論文の詳細を見る

• We review recent progress on the statiscal physics study of the problem of coloring random graphs with q colors. We discuss the existence of a threshold at connectivity c_q=2qlogq-logq-1+o(1) separting two phases which are respectivily COL (orable) and UNCOL (orable) with q colors; We also argue that the so-called one-step replica symmetry breaking ansatz used to derive these results give exact threshold values, and draw a general phase diagram of the problem.

• 理論物理学刊行会の論文
• 2005-04-30

著者

• KRZAKALA Florent

  Dipartimento di Fisica, INFM and SMC, Universita di Roma "La Sapienza"

• Krazakala Florent

  Dipartimento di Fisica, INFM and SMC, Universita di Roma "La Sapienza"

関連論文

• Quantum Annealing of Hard Problems(Frontiers in Nonequilibrium Physics-Fundamental Theory, Glassy & Granular Materials, and Computational Physics-)
• Zero Temperature Phase Diagram of Finite Connectivity Spin Glasses
• How Many Colors to Color a Random Graph? Cavity, Complexity, Stability and All That

スポンサーリンク