Spin systems on Bethe lattices

So far the problem of a spin glass on a Bethe lattice has been solved only at the replica symmetric level, which is wrong in the spin glass phase. Because of some technical difficulties, attempts at deriving a replica symmetry breaking solution have been confined to some perturbative regimes, high connectivity lattices or temperature close to the critical temperature. Using the cavity method, we propose a general non perturbative solution of the Bethe lattice spin glass pro...

A wide class of problems in combinatorics, computer science and physics can be described along the following lines. There are a large number of variables ranging over a finite domain that interact through constraints that each bind a few variables and either encourage or discourage certain value combinations. Examples include the $k$-SAT problem or the Ising model. Such models naturally induce a Gibbs measure on the set of assignments, which is characterised by its partition ...

We use the cavity method to study parallel dynamics of disordered Ising models on a graph. In particular, we derive a set of recursive equations in single site probabilities of paths propagating along the edges of the graph. These equations are analogous to the cavity equations for equilibrium models and are exact on a tree. On graphs with exclusively directed edges we find an exact expression for the stationary distribution of the spins. We present the phase diagrams for an ...

A theory for the complexity of the Bethe lattice spin-glass is developed applying to the cavity-method scheme of Mezard and Parisi the results recently obtained in the context of the Sherrington-Kirkpatrick model. The crucial ingredient is the introduction of a new cavity field z related to the marginality of the relevant states. The theory admits a variational formulation. In the high-connectivity limit it yields the Bray and Moore expression for the TAP complexity of the SK...

We introduce a version of the cavity method for diluted mean-field spin models that allows the computation of thermodynamic quantities similar to the Franz-Parisi quenched potential in sparse random graph models. This method is developed in the particular case of partially decimated random constraint satisfaction problems. This allows to develop a theoretical understanding of a class of algorithms for solving constraint satisfaction problems, in which elementary degrees of fr...

Bethe lattice spins glasses are supposed to be marginally stable, i.e. their equilibrium probability distribution changes discontinuously when we add an external perturbation. So far the problem of a spin glass on a Bethe lattice has been studied only using an approximation where marginally stability is not present, which is wrong in the spin glass phase. Because of some technical difficulties, attempts at deriving a marginally stable solution have been confined to some pertu...

We review critically the concepts and the applications of Cayley Trees and Bethe Lattices in statistical mechanics in a tentative effort to remove widespread misuse of these simple, but yet important - and different - ideal graphs. We illustrate, in particular, two rigorous techniques to deal with Bethe Lattices, based respectively on self-similarity and on the Kolmogorov consistency theorem, linking the latter with the Cavity and Belief Propagation methods, more known to the...

We first present an empirical study of the Belief Propagation (BP) algorithm, when run on the random field Ising model defined on random regular graphs in the zero temperature limit. We introduce the notion of maximal solutions for the BP equations and we use them to fix a fraction of spins in their ground state configuration. At the phase transition point the fraction of unconstrained spins percolates and their number diverges with the system size. This in turn makes the ass...

Given a locally consistent set of reduced density matrices, we construct approximate density matrices which are globally consistent with the local density matrices we started from when the trial density matrix has a tree structure. We employ the cavity method of statistical physics to find the optimal density matrix representation by slowly decreasing the temperature in an annealing algorithm, or by minimizing an approximate Bethe free energy depending on the reduced density ...

We study spin systems on Bethe lattices constructed from d-dimensional hypercubes. Although these lattices are not tree-like, and therefore closer to real cubic lattices than Bethe lattices or regular random graphs, one can still use the Bethe-Peierls method to derive exact equations for the magnetization and other thermodynamic quantities. We compute phase diagrams for ferromagnetic Ising models on hypercubic Bethe lattices with dimension d=2, 3, and 4. Our results are in go...