Journey trough statistical physics of constraint satisfaction.. by Lenka Zdeborova

Graph coloring

There appears to be a Phase transition w.r.t. to the average degree of the random graph, so that above a threshold, depending on the number of colors, the graph is not colorable w.h.p., and below it, it is colorable w.h.p.

Can define annealed, and quenched entropy (which is more indicative)...

Can show that asymptotically for large number of colors $q$, the threshold is $c_{col} \sim 2q\log{q}$. A simple greedy coloring algorithm "works" (I guess polynomially in average?) for $c < \frac{c_{col}}{2} \sim q\log{q}$. However, noone has been able to show any other algorithm that would "work" for any larger $c$ for random graphs.

On the Chromatic Number of Random Regular Graphs

– statistical formulation. Potts anti-ferromagnet spin model in a Random graph

How to compute the partition function on trees because (Partition function) Random graphs are locally tree-like

Factor graph as those found on Markov networks

We can analyze them through Belief propagation (vid), aka Cavity method

Local entropy as a measure for sampling solutions in constraint satisfaction problems

Finding proper colorings on random graph by decimation

Statistical physics and inference