Abstract:
Coloring of a graph with q colors is one of the most famous problems in discrete mathematics and an important benchmark in the theory of computational complexity. Studies of the average computational complexity of finding a coloring, or of showing that a proper coloring does not exist, has triggered the interest of statistical physicist in the problem.
Graph coloring is equivalent to the antiferromagnetic Potts model at zero temperature. The average case of the problem is modeled by the underlying lattice being a random graph. Mean field-like methods developed in studies of spin glasses appear to be precise in that case and give a tool to describe the phase diagram of the problem at both zero and finite temperature.
The systems undergoes several phase transitions when parameters like the connectivity of the graph or the temperature are tuned. In this seminar we will describe the methods leading to the understanding of this phase diagram, the nature of the several different phase transitions, and some algorithmic implications.