The threshold regime of finite volume bootstrap percolation

The emergence of connectivity in neuronal networks: from bootstrap percolation to auto-associative memory

We consider a random synaptic pruning in an initially highly interconnected network. It is proved that a random network can maintain a self-sustained activity level for some parameters. For such a set of parameters a pruning is constructed so that in the resulting network each neuron/node has almost equal numbers of in- and out-connections. It is also shown that the set of parameters which admits a self-sustained activity level is rather small within the whole space of possible parameters. It is pointed out here that the threshold of connectivity for an auto-associative memory in a Hopfield model on a random graph coincides with the threshold for the bootstrap percolation on the same random graph. It is argued that this coincidence reflects the relations between the auto-associative memory mechanism and the properties of the underlying random network structure. This article is part of a Special Issue entitled "Neural Coding".

k-core percolation in four dimensions

The k-core percolation on the Bethe lattice has been proposed as a simple model of the jamming transition because of its hybrid first-order-second-order nature. We investigate numerically k-core percolation on the four-dimensional regular lattice. For k=4 , the presence of a discontinuous transition is clearly established but its nature is strictly first-order. In particular, the k-core density displays no singular behavior before the jump and its correlation length remains finite. For k=3, the transition is continuous.

Culling avalanches in bootstrap percolation

We study the culling avalanches which occur after the "death" of a single randomly chosen site in a network where sites are unstable, and are culled, if they have coordination less than an integer parameter m. Avalanche distributions are presented for triangular and cubic lattices for values of m where the associated bootstrap transitions are either first or second order. In second order cases, the culling avalanche distribution is found to be exponential, while in first order cases it follows a power law. We present an exact relation between culling avalanches and conventional bootstrap percolation and show that a relation proposed by Manna [Physica A 261, 351 (1998)] can be a good approximation for strongly first order bootstrap transitions but not for continuous bootstrap transitions.

Exact solution of a jamming transition: closed equations for a bootstrap percolation problem

Jamming, or dynamical arrest, is a transition at which many particles stop moving in a collective manner. In nature it is brought about by, for example, increasing the packing density, changing the interactions between particles, or otherwise restricting the local motion of the elements of the system. The onset of collectivity occurs because, when one particle is blocked, it may lead to the blocking of a neighbor. That particle may then block one of its neighbors, these effects propagating across some typical domain of size named the dynamical correlation length. When this length diverges, the system becomes immobile. Even where it is finite but large the dynamics is dramatically slowed. Such phenomena lead to glasses, gels, and other very long-lived nonequilibrium solids. The bootstrap percolation models are the simplest examples describing these spatio-temporal correlations. We have been able to solve one such model in two dimensions exactly, exhibiting the precise evolution of the jamming correlations on approach to arrest. We believe that the nature of these correlations and the method we devise to solve the problem are quite general. Both should be of considerable help in further developing this field.

Clarification of the bootstrap percolation paradox

We study the onset of the bootstrap percolation transition as a model of generalized dynamical arrest. Our results apply to two dimensions, but there is no significant barrier to extending them to higher dimensionality. We develop a new importance-sampling procedure in simulation, based on rare events around "holes", that enables us to access bootstrap lengths beyond those previously studied. By framing a new theory in terms of paths or processes that lead to emptying of the lattice we are able to develop systematic corrections to the existing theory and compare them to simulations. Thereby, for the first time in the literature, it is possible to obtain credible comparisons between theory and simulation in the accessible density range.

Spatial structures and dynamics of kinetically constrained models of glasses

Kob and Andersen's simple lattice models for the dynamics of structural glasses are analyzed. Although the particles have only hard core interactions, the imposed constraint that they cannot move if surrounded by too many others causes slow dynamics. On Bethe lattices, a dynamical transition to a partially frozen phase occurs. In finite dimensions there exist rare mobile elements that destroy the transition. At low vacancy density v, the spacing Xi between mobile elements diverges exponentially or faster in 1/v. Within the mobile elements, the dynamics is intrinsically cooperative, and the characteristic time scale diverges faster than any power of 1/v (although slower than Xi). The tagged-particle diffusion coefficient vanishes roughly as Xi(-d).