6
Compaction of disordered grains in the jamming limit:
sand on random graphs
Granular compaction is characterised by a competition between fast and slow
degrees of freedom [69]; far from the jamming limit, individual grains can
quickly move into suitable voids in their neighbourhood. As the jamming limit
is approached, however, voids which can accommodate whole grains become more
and more rare; a cooperative rearrangement of grain clusters is required to fill the
partial voids which remain. Such collective processes are necessarily slow, and
eventually lead to dynamical arrest [149, 150].
The modelling of granular compaction has been the subject of considerable effort.
Early simulations of shaken hard sphere packings [61, 62, 130], carried out in close
symbiosis with experiment [172, 173], were followed by lattice-based theoretical
models [75, 174, 175]; the latter could not, of course, incorporate the reality of a
disordered substrate. Mean-field models [176] which could incorporate such disor-
der could not, on the other hand, impose the finite connectivity of grains included
in Refs. [61, 62, 75, 130, 174, 175]. It was to answer the need of an analytically
tractable model which incorporated finitely connected grains on fully disordered
substrates that random graph models of granular compaction were first introduced
by Berg and Mehta [152, 153].
A random graph [177] consists of a set of nodes and bonds, with the bonds
connecting each node at random to a finite number of others, thus, from the point
of view of connectivity, appearing like a finite-dimensional structure. Each bond
may link two sites (a graph) or more (a so-called hypergraph). Why are random
graphs useful for modelling granular physics? First, random graphs [177] are the
simplest structures containing nodes with a finite number of neighbours. Clearly,
real grains are always connected to a finite number of neighbours as evinced by
their finite coordination numbers [61]; that this is a key property of grains with
important physical consequences, ranging from kinetic constraints [178] to the
Granular Physics, ed. Anita Mehta. Published by Cambridge University Press.
C

first. Choosing C
ijk
= 1(0) randomly with probability 2c/N
2
(1 − 2c/N
2
) results
in a random three-hypergraph, where the number of plaquettes connected to a site
is distributed with a Poisson distribution of average c. An illustration of part of
such a graph is shown in Fig. 6.1. Next, a specific spin model will be defined on
this graph. Spin models on random graphs have been investigated for many years
6.1 The three-spin model of granular compaction 81
[179], being halfway between infinite-connectivity models and finite-dimensional
models; this leads to their having the analytic accessibility of the former within
the framework of mean-field theory, as well as the finite connectivity of the latter.
Interest in these models has intensified lately since they occur in the context of
random combinatorial optimization problems [180] and inroads have been made
towards their analytic treatment beyond replica-symmetry.
Having motivated our choice of random graphs as a basis, we proceed below to
describe the first [152, 153] of many spin models of granular compaction.
6.1 The three-spin model: frustration, metastability and slow dynamics
The guiding factor in this choice of spin model is that it be the simplest model with
frustration, metastability and slow dynamics; we will discuss the last two later, but
remark at the outset that geometrical frustration is crucial to any study of granular
matter. This concerns the fruitless competition between grains which try – and fail
– to fill voids in the jamming limit, due either to geometric constraints on their
mobility, or because of incompatibilities in shape or size. Our way of modelling
this is via multi-spin interactions on plaquettes on a random graph [152, 153]. We
choose in particular a three-spin Hamiltonian on a random graph (see Fig. 6.1)
where N binary spins S

ular compaction is made in accordance with Edwards’ hypothesis [15], which
assigns a thermodynamic ‘energy’ to the volume of a granular system: we, in
our turn, interpret the local contribution to the energy in different configurations
of the spins as the volume occupied by grains in different local orientations,in
Eq. 6.1.
This Hamiltonian has been studied on a random graph in various contexts
[181, 182]. It has a trivial ground state where all spins point up and all plaque-
ttes are in the configuration+++giving a contribution of−1 to the ‘energy’. Yet,
locally, plaquettes of the type −−+,−+−,+−− (satisfied plaquettes) also
give the same contribution; however, covering the graph with these mixed states
will typically result in frustration of some of the interfacial spins. The competition
between satisfying plaquettes locally and globally, given this degeneracy of the four
82 Sand on random graphs
configurations of plaquettes with s
i
s
j
s
k
= 1, thus results in frustration. Also, since
there are many possible ways of using the mixed states −−+,−+−,+−−to
cover the graph, which correspond to the various local minima on the ‘energy’ land-
scape of the system, there is a large entropy associated with these low-lying, nearly
degenerate ‘energy’ states. On the other hand, there is only one way of covering
the graph with the +++state, which of course corresponds to the global mini-
mum of the ‘energy’. It is therefore more probable that a typical minimisation of the
‘energy’ in Eq. 6.1 will lead to a mixed state, one of the many optimal arrangements
of the −−+,−+−,+−−states; however, any such optimal state will not be
the global minimum, and will always be in a state of frustration, due to mutual
dissatisfaction of some plaquettes. The system will always try to ‘do better’, and its

of energy +1 (the plaquette is unsatisfied) are indicated by a white dot.
treat each tap as consisting of two phases. First, during the dilation phase, grains
are provided with free volume to move into; next, in the quench phase, they are
allowed to relax until a mechanically stable configuration is reached.
More technically, the dilation phase is modelled by a single sequential Monte
Carlo sweep of the system at a dimensionless temperature . A site i is chosen at
random and flipped with probability 1 if its spin s
i
is antiparallel to its local field
h
i
, with probability exp(−h
i
/) if it is not, and with probability 0.5ifh
i
= 0. This
procedure is repeated N times. Sites with a large absolute value of the local field h
i
thus have a low probability of flipping into the direction against the field; such spins
may be thought of as being highly constrained by their neighbours. The dynamics
of this ‘thermal’ dilation phase differs from the ‘zero-temperature’ dynamics used
in [183] where a certain fraction of spins is flipped regardless of the value of their
local field. The choice used here [152, 153] reflects the following physics: if grains
are densely packed (‘strongly bonded’ to their neighbours), they are unlikely to be
displaced during the dilation phase of vibration.
The grains are then allowed to relax via a  = 0 quench, which lasts until the
system has reached a blocked configuration
1
where each site i has s
i

a logarithmic growth of the density via slow collective dynamics. The last regime
consists of system-spanning density fluctuations in the jamming limit, where quan-
titative agreement with experiment [184] allows one to propose a cascade theory
of compaction during jamming.
6.3.1 Fast dynamics till SPRT: every grain for itself!
At the end of the first tap, each grain is connected to more (or as many) unfrustrated
than frustrated clusters. This is a direct result of the first tap being a zero-temperature
quench: any site where this was not the case would simply flip its spin. More
generally, a fast dynamics occurs in this regime whereby single grains locally