Metastable configurations of spin models on random graphs

Statistical mechanics of maximal independent sets

The graph theoretic concept of maximal independent set arises in several practical problems in computer science as well as in game theory. A maximal independent set is defined by the set of occupied nodes that satisfy some packing and covering constraints. It is known that finding minimum and maximum-density maximal independent sets are hard optimization problems. In this paper, we use cavity method of statistical physics and Monte Carlo simulations to study the corresponding constraint satisfaction problem on random graphs. We obtain the entropy of maximal independent sets within the replica symmetric and one-step replica symmetry breaking frameworks, shedding light on the metric structure of the landscape of solutions and suggesting a class of possible algorithms. This is of particular relevance for the application to the study of strategic interactions in social and economic networks, where maximal independent sets correspond to pure Nash equilibria of a graphical game of public goods allocation.

Metastable configurations of small-world networks

We calculate the number of metastable configurations of Ising small-world networks that are constructed upon superimposing sparse Poisson random graphs onto a one-dimensional chain. Our solution is based on replicated transfer-matrix techniques. We examine the denegeracy of the ground state and find a jump in the entropy of metastable configurations exactly at the crossover between the small-world and the Poisson random graph structures. We also examine the difference in entropy between metastable and all possible configurations, for both ferromagnetic and bond-disordered long-range couplings.

Metastable configurations on the Bethe lattice

We present a general analytic method to compute the number of metastable configurations as a function of the energy for a system of interacting Ising spins on the Bethe lattice. Our approach is based on the cavity method. We apply it to the case of ferromagnetic interactions, and also to the binary and Gaussian spin glasses. Most of our results are obtained within the replica symmetric ansatz, but we illustrate how replica symmetry breaking can be performed.

Effective dynamics and steady state of an Ising model submitted to tapping processes

A one-dimensional Ising model with nearest neighbor interactions is applied to study compaction processes in granular media. An equivalent particle-hole picture is introduced, with the holes being associated to the domain walls of the Ising model. Trying to mimic the experiments, a series of taps separated by large enough waiting times, for which the system freely relaxes, is considered. The free relaxation of the system corresponds to a T=0 dynamics which can be analytically solved. There is an extensive number of metastable states, characterized by all the holes being isolated. In the limit of weak tapping, an effective dynamics connecting the metastable states is obtained. The steady state of this dynamics is analyzed, and the probability distribution function is shown to have the canonical form. Then, the stationary state is described by Edwards thermodynamic granular theory. Spatial correlation functions in the steady state are also studied.

Glassy dynamics in granular compaction: sand on random graphs

We discuss the use of a ferromagnetic spin model on a random graph to model granular compaction. A multispin interaction is used to capture the competition between local and global satisfaction of constraints characteristic for geometric frustration. We define an athermal dynamics designed to model repeated taps of a given strength. Amplitude cycling and the effect of permanently constraining a subset of the spins at a given amplitude is discussed. Finally we check the validity of Edwards's hypothesis for the athermal tapping dynamics.