Circular Coloring of Random Graphs: Statistical Physics Investigation

Christian Schmidt 1 Nils-Eric Guenther 2, 1 Lenka Zdeborová 1
1 IPHT - Institut de Physique Théorique - UMR CNRS 3681
2 ICFO - Institut de Ciencies Fotoniques [Castelldefels]
Abstract : Circular coloring is a constraints satisfaction problem where colors are assigned to nodes in a graph in such a way that every pair of connected nodes has two consecutive colors (the first color being consecutive to the last). We study circular coloring of random graphs using the cavity method. We identify two very interesting properties of this problem. For sufficiently many color and sufficiently low temperature there is a spontaneous breaking of the circular symmetry between colors and a phase transition forwards a ferromagnet-like phase. Our second main result concerns 5-circular coloring of random 3-regular graphs. While this case is found colorable, we conclude that the description via one-step replica symmetry breaking is not sufficient. We observe that simulated annealing is very efficient to find proper colorings for this case. The 5-circular coloring of 3-regular random graphs thus provides a first known example of a problem where the ground state energy is known to be exactly zero yet the space of solutions probably requires a full-step replica symmetry breaking treatment.
Type de document :
Article dans une revue
Journal of Statistical Mechanics: Theory and Experiment, IOP Science, 2016, 2016 (8), pp.83303. 〈10.1088/1742-5468/2016/08/083303〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger
https://hal-cea.archives-ouvertes.fr/cea-01585492
Contributeur : Emmanuelle De Laborderie <>
Soumis le : lundi 11 septembre 2017 - 15:37:20
Dernière modification le : jeudi 15 mars 2018 - 15:06:13

Fichier

1605.06945.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

CEA | DSM-IPHT | UNIV-PARIS-SACLAY | CEA-DRF | CEA-UPSAY

Citation

Christian Schmidt, Nils-Eric Guenther, Lenka Zdeborová. Circular Coloring of Random Graphs: Statistical Physics Investigation. Journal of Statistical Mechanics: Theory and Experiment, IOP Science, 2016, 2016 (8), pp.83303. 〈10.1088/1742-5468/2016/08/083303〉. 〈cea-01585492〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

75

Téléchargements de fichiers

28

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD