We study the magnetization of the ferromagnetic Ising model on sparse random graphs. In the limit of large system size, such graphs converge locally to trees, meaning that the Bethe (also known as the `cavity method') approximations of the free energy and other thermodynamic quantities are asymptotically exact. In our case this means that local magnetizations can be computed via a system of self-consistent equations in terms of ‘cavity magnetizations’. We think of these as messages which a node sends to its neighbor , estimating the local magnetization at but disregarding the coupling . Moreover, it has been demonstrated that in the thermodynamic limit, it is sufficient to convert this self-consistent scheme to a recursive distributional equation relating the ensemble of these messages to the distribution of excess degrees in the underlying graph. In this work we attempt to characterize those degree distributions which maximize the average magnetization for a €fixed average degree and inverse temperature , relating the optimal distributions to a bizarre ensemble of fictitious regular graphs with non-integer degrees.
Noyce Conference Room
This event is by invitation only.
Sparse Graphs with Maximal Ising MagnetizationIn collaboration with Florent Kzrakala, Cristopher Moore, Lenka Zdeborová, and Pan Zhang