skip to main content

Phase Transitions in the Coloring of Random Graphs

Zdeborová, Lenka ; Krzakala, Florent ; Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS) ; Université Paris-Sud - Paris 11 (UP11) - Centre National de la Recherche Scientifique (CNRS) ; Laboratoire de Physico-Chimie Théorique (LPCT) ; ESPCI ParisTech - Centre National de la Recherche Scientifique (CNRS)

ISSN: 1539-3755

HAL CCSD;American Physical Society, 2007

Accessible en ligne

  • Titre:
    Phase Transitions in the Coloring of Random Graphs
  • Auteur: Zdeborová, Lenka;
    Krzakala, Florent
  • Autre(s) auteur(s): Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS) ; Université Paris-Sud - Paris 11 (UP11) - Centre National de la Recherche Scientifique (CNRS);
    Laboratoire de Physico-Chimie Théorique (LPCT) ; ESPCI ParisTech - Centre National de la Recherche Scientifique (CNRS)
  • Sujets: [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC]; [PHYS.COND.CM-SM] Physics [physics]/Condensed Matter [cond-mat]/Statistical Mechanics [cond-mat.stat-mech]
  • Fait partie de: ISSN: 1539-3755
  • Description: 36 pages, 15 figures
    International audience
    We consider the problem of coloring the vertices of a large sparse random graph with a given number of colors so that no adjacent vertices have the same color. Using the cavity method, we present a detailed and systematic analytical study of the space of proper colorings (solutions). We show that for a fixed number of colors and as the average vertex degree (number of constraints) increases, the set of solutions undergoes several phase transitions similar to those observed in the mean field theory of glasses. First, at the clustering transition, the entropically dominant part of the phase space decomposes into an exponential number of pure states so that beyond this transition a uniform sampling of solutions becomes hard. Afterward, the space of solutions condenses over a finite number of the largest states and consequently the total entropy of solutions becomes smaller than the annealed one. Another transition takes place when in all the entropically dominant states a finite fraction of nodes freezes so that each of these nodes is allowed a single color in all the solutions inside the state. Eventually, above the coloring threshold, no more solutions are available. We compute all the critical connectivities for Erdos-Renyi and regular random graphs and determine their asymptotic values for large number of colors. Finally, we discuss the algorithmic consequences of our findings. We argue that the onset of computational hardness is not associated with the clustering transition and we suggest instead that the freezing transition might be the relevant phenomenon. We also discuss the performance of a simple local Walk-COL algorithm and of the belief propagation algorithm in the light of our results.
  • Titres liés: info:eu-repo/semantics/altIdentifier/arxiv/0704.1269
  • Éditeur: HAL CCSD;American Physical Society
  • Date de publication: 2007
  • Langue: Anglais
  • Identifiant: HAL Id hal--00176651 ; ARXIV : 0704.1269
  • Source: ESPCI Paris (archives ouvertes)

Recherche dans les bases de données distantes en cours. Merci de patienter.

  • Recherche
  • dansscope:(33PSL-CNSAD),scope:(33PSL-EHESS),scope:(33PSL-PSL_OMEKA),scope:(33PSL-MINES),scope:(33PSL-EFEO),scope:(33PSL-CNSMDP),scope:(33PSL-CHIMIE),scope:(33PSL),scope:("DAU"),scope:(33PSL-CDF),scope:(33PSL-ENS),scope:("33PSL-OBSERV"),scope:("33PSL-ESPCI"),scope:(33PSL-CURIE),scope:(33PSL-ENSBA),scope:("33PSL-ENC"),scope:(33PSL-PSL_STAR),scope:(33PSL-PSL_SFX),scope:("33PSL-EPHE"),scope:(33PSL-ENSAD),primo_central_multiple_fe
  • Afficher ce qui a déjà été récupéré