Circular Coloring of Random Graphs: Statistical Physics Investigation
arXiv:1605.06945 · doi:10.1088/1742-5468/2016/08/083303
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.
arXiv comment19 pages, 8 figures, 3 tables
References in corpus (11)
- The Bethe lattice spin glass revisited
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- On the Out of Equilibrium Relaxation of the Sherrington - Kirkpatrick model
- Phase Transitions in the Coloring of Random Graphs
- Coloring random graphs
- Polynomial iterative algorithms for coloring and analyzing random graphs
- Landscape of solutions in constraint satisfaction problems
- The asymptotic -SAT threshold
- The condensation transition in random hypergraph 2-coloring
- The condensation phase transition in random graph coloring
- Conjecture on the maximum cut and bisection width in random regular graphs