Circular coloring of random graphs: statistical physics investigation

DOI10.1088/1742-5468/2016/08/083303MaRDI QIDQ3302790zbMATH OpenOpenAlexFDO

Authors Christian Schmidt, Nils-Eric Guenther, Lenka Zdeborová

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.06945

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80)

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.

Recommendations

• Coloring random graphs
• The condensation phase transition in random graph coloring
• Constraining the clustering transition for colorings of sparse random graphs
• Phase transitions in the \(q\)-coloring of random hypergraphs
• The condensation phase transition in random graph coloring

Cites work

• A Combinatorial Classic — Sparse Graphs with High Chromatic Number
• Coloring random graphs
• Colorings and homomorphisms of degenerate and bounded degree graphs
• Gibbs states and the set of solutions of random constraint satisfaction problems
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• Information, Physics, and Computation
• On the out-of-equilibrium relaxation of the Sherrington-Kirkpatrick model
• Random cubic graphs are not homomorphic to the cycle of size 7
• Random graphs.
• Recent developments in circular colouring of graphs
• Regular graphs with no homomorphisms onto cycles
• Survey propagation: An algorithm for satisfiability
• The asymptotic k-SAT threshold
• The cavity method at zero temperature
• The condensation phase transition in random graph coloring
• The condensation transition in random hypergraph 2-coloring
• Tight bounds on the threshold for permuted k-colorability
• Upper-bounding the k-colorability threshold by counting covers

Cited in

(3)

• Phase transitions in the \(q\)-coloring of random hypergraphs
• Satisfiability thresholds for regular occupation problems
• Satisfiability thresholds for regular occupation problems

This page was built for publication: Circular coloring of random graphs: statistical physics investigation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3302790)