Gibbs measures and phase transitions on sparse random graphs (Q985984)

Many problems in probability, theoretical computer science and theoretical physics study a set of random variables associated with the vertices of a large (but finite) sparse graph, a natural way to generate ``locally dependent'' collections of random variables. However there is a large gap between what physicists have satisfied themselves of via heuristic arguments and what has been rigorously proven. This article is a contribution to the rigorous theory in this direction for sparse random graphs. While these are not contained in lattices, implying that the direct link with physics is lost, one might hope, via some ``universality'' ideas, that at least some of the structure emerging might subsist in lattice models too. We take a graph \(G=(V,E)\) with each vertex \(i\in V\) having an attached variable \(x_{i}\) taking values in a finite set \( {\mathcal X}\). To each edge \(ij\) of \(G\) associate a map \(\psi_{ij}: {\mathcal X}\times {\mathcal X}\rightarrow [0,\psi_{max}]\) for a constant \(\psi_{max}\): note \(\psi_{ij}=\psi_{ji}\). We may also have a function \(\psi_{i}\) from each vertex to \({\mathcal X}\). We then form the canonical probability measure \(\mu_{G,\psi}\) associated to \(G\) and this collection \(\underline{\psi}\) of maps \(\psi_{ij}\) and \(\psi_{i}\): \[ \mu_{G,\psi}=\frac{1}{Z(G,\underline{\psi})}\prod_{ij\in E(G)}\psi_{ij}(x_{i},x_{j})\prod_{i\in V}\psi_{i}(x_{i}) \] where \(Z(G,\underline{\psi})\) is a normalising constant. A special case much studied is the Curie-Weiss model where \(x_{i}=\pm 1\), \(G=K_{n}\) and \(\psi_{ij}(x_{i},x_{j})=\exp(\beta x_{i}x_{j}/n)\), or the generalised Curie-Weiss model with additionally a ``magnetic field'' given by \(\psi_{i}(x_{i})=\exp(B x_{i})\). Other examples include the Ising model (basically, the generalised Curie-Weiss model on a more general \(n\)-vertex graph \(G\) than \(K_{n}\): here one tends to use \(Z_{n}(\beta,B)\) rather than \(Z(G,\psi)\), \(G\) being quietly understood), `spin glasses', various random constraint satisfaction problems, proper colourings of graphs and various problems in communications. The rest of this review concentrates on broad ideas rather than detail. We say a model \((G,\underline{\psi})\) displays ``coexistence'' if \(\mu_{G,\underline{\psi}}\) decomposes into a convex combination of well-separated lumps, with bottlenecks between them. When this is suitably formalised, it turns out that the generalised Curie-Weiss model exhibits such coexistence if and only if \(\beta>1\) and \(B=0\). Chapter 2 of the article deals with the Ising model on sparse graphs that `converge locally to conditionally independent trees': one makes this precise and shows that a sequence of sparse graphs \(G(n,p)\) with \(p=c/n\) do converge to one such tree, the Galton-Watson tree. In these circumstances one can prove results about the decay of correlations with increasing graph distance in the graphs. A (rigorous form of) Bethe-Peierls approximation for certain particular graph sequences now gives the limiting behaviour of the asymptotic free energy density \(\lim_{n\rightarrow\infty}\frac{1}{n}\log (Z_{n}(\beta,B)\), leading to (e.g.) the conclusion that the ferromagnetic Ising measures on random \(k\)-regular multigraphs from the configuration model exhibit coexistence if and only if \((k-1)\tanh(\beta)>1\). Chapter 3 studies Bethe-Peierls approximation, which turns the computation of partition functions into solving (messy) non-linear equations: for mean field models (roughly, those without finite-dimensional geometric structure) physicists think this should be asymptotically exact. The main result is that the Bethe approximation does hold when the graph is tree-like and there is a suitable decay hypothesis on correlations, which generalises the `extremality condition', in trees. Chapter 4 is on proper \(q\)-colourings (\(q\) fixed). Now the canonical measure is \(\prod_{ij\in E(G)}I(x_{i}\neq x_{j})\) divided by the number \(Z_{G}\) of proper \(q\)-colourings. As the number of edges (assumed linear in the number of vertices) increases, there should be a threshold for the transition from \(q\)-colourable to not \(q\)-colourable but this is not proven yet. For random \((k+1)\)-regular graphs, \(\mu_{G}\) should exhibit co-existence (say the physicists) if and only if a certain fixed point equation admits a non-trivial solution when a certain parameter \(\epsilon\) is zero. This equation is also linked with solubility of a reconstruction problem for trees (the reconstruction threshold is, roughly, the point where the colour of the root of the tree moves from being uncorrelated with that of a distant point to being correlated), and (heuristically) with the growth rate of the number of `clusters', into which \(\mu_{G}\) decomposes. This leads into a discussion in Chapter 5 of reconstruction and extremality. The main result is that reconstruction on the real graph and on the tree approximating it are equivalent under a `sphericity', condition. The reconstruction problem is linked to MCMC and random constraint satisfaction problems.