Gibbs Measures on Trees and Random Graphs

Understanding Gibbs measures on trees and their spatial mixing thresholds (uniqueness, strong spatial mixing, reconstruction) can give insight into the behavior of Gibbs measures on general graphs, in particular random graphs which are locally tree-like. We discuss two results: In the first result, we show that counter to the general notion that the d regular tree is the worst case for decay of correlation between sets and nodes among all d regular graphs, we produce an example of a spin interacting system which has uniqueness on the d-regular tree but does not have uniqueness on some infinite d-regular graphs.

In the second result we overcome an obstacle of most techniques for analysing the mixing time of the Glauber dynamics, i.e., that they are stated in terms of maximal degree and are therefore insufficient for Erdos Renyi random graphs where the maximum degree grows as order (logn)/(log log n). We show that for most natural models defined on G(n,d/n) if the “temperature” is high enough (as a function of d only) then the mixing time of Glauber dynamics is polynomial. This proves in particular a conjecture of Dyer et.al. proving rapid mixing of random colourings on G(n,d/n) with a constant number of colours.