Spectral bounds for the Ising ferromagnet on an arbitrary given graph. (18th May 2017) - Saade, Alaa; Krzakala, Florent; Zdeborová, Lenka
Abstract: We revisit classical bounds of Fisher on the ferromagnetic Ising model (Fisher 1967 Phys. Rev .162 480), and show how to efficiently use them on an arbitrary given graph to rigorously upper-bound the partition function, magnetizations, and correlations. The results are valid on any finite graph, with arbitrary topology and arbitrary positive couplings and fields. Our results are based on high temperature expansions of the aforementioned quantities, and are expressed in terms of two related linear operators: the non-backtracking operator and the Bethe Hessian. As a by-product, we show that in a well-defined high-temperature region, the susceptibility propagation algorithm (Mezard 2009 J. Physiol .103 107–13) converges and provides an upper bound on the true spin–spin correlations.