Dresden 2003 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

DY: Dynamik und Statistische Physik

DY 51: Statistical physics (general) I

DY 51.3: Talk

Friday, March 28, 2003, 10:45–11:00, G\"OR/229

Coloring random graphs — •Martin Weigt¹, Roberto Mulet², Andrea Pagnani³, and Riccardo Zecchina⁴ — ¹Institut für Theoretische Physik, Uni Göttingen, Bunsenstr. 9, 37073 Göttingen — ²University of Havana, Cuba — ³Universita di Roma “La Sapienza”, Italy — ⁴ICTP Trieste, Italy

We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, we find that graphs with low connectivity admit almost always a proper coloring whereas graphs with high connectivity are uncolorable. Depending on q, we find the precise value of the critical average connectivity c_q. Moreover, we show that below c_q there exist a clustering phase c∈ [c_d,c_q] in which ground states spontaneously divide into an exponential number of clusters and where the proliferation of metastable states is responsible for the onset of complexity in local search algorithms.