Random Sequential Adsorption on Random Trees

When gas molecules bind to a surface they may do so in such a way that the adsorption of one molecule inhibits the arrival of others. Two models which have frequently been studied are the “dimer model” and the “blocking model”, and rather complete solutions for these are known on fixed tree structures or Bethe lattices. In this paper comparisons are made between the occupation probabilities for vertices between fixed and random trees.     

Mean-Field Criticality for Percolation on Planar Non-Amenable Graphs

The critical exponents β, γ, δ and Δ are proved to exist and to take their mean-field values for independent percolation on the following classes of infinite, locally finite, connected transitive graphs: (1) Non-amenable planar with one end. (2) Unimodular with infinitely many ends. Received: 4 April 2001 / Accepted: 4 October 2001     

Limit Theorems for Random Point Measures Generated by Cooperative Sequential Adsorption

We consider a finite sequence of random points in a finite domain of finite-dimensional Euclidean space. The points are sequentially allocated in the domain according to the model of cooperative sequential adsorption. The main peculiarity of the model is that the probability distribution of any point depends on previously allocated points. We assume that the dependence vanishes as the concentration of points tends to infinity. Under this assumption the law of large numbers, Poisson approximation and the central limit theorem are proved for the generated sequence of random point measures.     

Isolation and Connectivity in Random Geometric Graphs with Self-similar Intensity Measures

Random geometric graphs consist of randomly distributed nodes (points), with pairs of nodes within a given mutual distance linked. In the usual model the distribution of nodes is uniform on a square, and in the limit of infinitely many nodes and shrinking linking range, the number of isolated nodes is Poisson distributed, and the probability of no isolated nodes is equal to the probability the whole graph is connected. Here we examine these properties for several self-similar node distributions, including smooth and fractal, uniform and nonuniform, and finitely ramified or otherwise. We show that nonuniformity can break the Poisson distribution property, but it strengthens the link between isolation and connectivity. It also stretches out the connectivity transition. Finite ramification is another mechanism for lack of connectivity. The same considerations apply to fractal distributions as smooth, with some technical differences in evaluation of the integrals and analytical arguments.     

Random Parking, Sequential Adsorption,¶and the Jamming Limit

Identical cars are dropped sequentially from above into a large parking lot. Each car is positioned uniformly at random, subject to non-overlap with its predecessors, until jamming occurs. There have been many studies of the limiting mean coverage as the parking lot becomes large, but no complete proof that such a limit exists, until now. We prove spatial laws of large numbers demonstrating that for various multidimensional random and cooperative sequential adsorption schemes such as the one above, the jamming limit coverage is well-defined. Received: 18 August 2000 / Accepted: 13 November 2000     

Swarming on Random Graphs

We consider a compromise model in one dimension in which pairs of agents interact through first-order dynamics that involve both attraction and repulsion. In the case of all-to-all coupling of agents, this system has a lowest energy state in which half of the agents agree upon one value and the other half agree upon a different value. The purpose of this paper is to study the behavior of this compromise model when the interaction between the N agents occurs according to an Erd?s-Rényi random graph $\mathcal{G}(N,p)$ . We study the effect of changing p on the stability of the compromised state, and derive both rigorous and asymptotic results suggesting that the stability is preserved for probabilities greater than $p_{c}=O(\frac{\log N}{N})$ . In other words, relatively few interactions are needed to preserve stability of the state. The results rely on basic probability arguments and the theory of eigenvalues of random matrices.     

Multiplicity of Phase Transitions and Mean-Field Criticality on Highly Non-Amenable Graphs

We consider independent percolation, Ising and Potts models, and the contact process, on infinite, locally finite, connected graphs. It is shown that on graphs with edge-isoperimetric Cheeger constant sufficiently large, in terms of the degrees of the vertices of the graph, each of the models exhibits more than one critical point, separating qualitatively distinct regimes. For unimodular transitive graphs of this type, the critical behaviour in independent percolation, the Ising model and the contact process are shown to be mean-field type. For Potts models on unimodular transitive graphs, we prove the monotonicity in the temperature of the property that the free Gibbs measure is extremal in the set of automorphism invariant Gibbs measures, and show that the corresponding critical temperature is positive if and only if the threshold for uniqueness of the infinite cluster in independent bond percolation on the graph is less than 1. We establish conditions which imply the finite-island property for independent percolation at large densities, and use those to show that for a large class of graphs the q-state Potts model has a low temperature regime in which the free Gibbs measure decomposes as the uniform mixture of the q ordered phases. In the case of non-amenable transitive planar graphs with one end, we show that the q-state Potts model has a critical point separating a regime of high temperatures in which the free Gibbs measure is extremal in the set of automorphism-invariant Gibbs measures from a regime of low temperatures in which the free Gibbs measure decomposes as the uniform mixture of the q ordered phases. Received: 27 March 2000 / Accepted: 7 December 2000     

Critical Behavior of the Annealed Ising Model on Random Regular Graphs

In Giardinà et al. (ALEA Lat Am J Probab Math Stat 13(1):121–161, 2016), the authors have defined an annealed Ising model on random graphs and proved limit theorems for the magnetization of this model on some random graphs including random 2-regular graphs. Then in Can (Annealed limit theorems for the Ising model on random regular graphs, arXiv:1701.08639, 2017), we generalized their results to the class of all random regular graphs. In this paper, we study the critical behavior of this model. In particular, we determine the critical exponents and prove a non standard limit theorem stating that the magnetization scaled by \(n^{3/4}\) converges to a specific random variable, with n the number of vertices of random regular graphs.     

The Einstein Relation for Random Walks on Graphs

This paper investigates the Einstein relation; the connection between the volume growth, the resistance growth and the expected time a random walk needs to leave a ball on a weighted graph. The Einstein relation is proved under different set of conditions. In the simplest case it is shown under the volume doubling and time comparison principles. This and the other set of conditions provide the basic framework for the study of (sub-) diffusive behavior of the random walks on weighted graphs.     

Scaling Properties of the Number of Random Sequential Adsorption Iterations Needed to Generate Saturated Random Packing

The properties of the number of iterations in random sequential adsorption protocol needed to generate finite saturated random packing of spherically symmetric shapes were studied. Numerical results obtained for one, two, and three dimensional packings were supported by analytical calculations valid for any dimension d. It has been shown that the number of iterations needed to generate finite saturated packing is subject to Pareto distribution with exponent \(-1-1/d\) and the median of this distribution scales with packing size according to the power-law characterized by exponent d. Obtained results can be used in designing effective random sequential adsorption simulations.     

Random Sequential Adsorption: Relationship to Dead Leaves and Characterization of Variability

A new construction for the planar unbounded random sequential adsorption (RSA) model is presented, which allows for a direct comparison with Matheron's dead leaves model. Furthermore, for the case of disks with random radii the problem of statistical determination of the proposal radius distribution is discussed. Finally, second order characteristics related to the pair correlation function are suggested for describing the variability of the RSA disk systems.     

Glauber Dynamics for the Mean-Field Potts Model

We study Glauber dynamics for the mean-field (Curie-Weiss) Potts model with q??3 states and show that it undergoes a critical slowdown at an inverse-temperature ?? _s (q) strictly lower than the critical ?? _c (q) for uniqueness of the thermodynamic limit. The dynamical critical ?? _s (q) is the spinodal point marking the onset of metastability. We prove that when ??<?? _s (q) the mixing time is asymptotically C(??,q)nlogn and the dynamics exhibits the cutoff phenomena, a sharp transition in mixing, with a window of order n. At ??=?? _s (q) the dynamics no longer exhibits cutoff and its mixing obeys a power-law of order n ^4/3. For ??>?? _s (q) the mixing time is exponentially large in n. Furthermore, as ?????? _s with n, the mixing time interpolates smoothly from subcritical to critical behavior, with the latter reached at a scaling window of O(n ^?2/3) around ?? _s . These results form the first complete analysis of mixing around the critical dynamical temperature??including the critical power law??for a model with a first order phase transition.     

Large Deviations for the Annealed Ising Model on Inhomogeneous Random Graphs: Spins and Degrees

Journal of Statistical Physics - We prove a large deviations principle for the total spin and the number of edges under the annealed Ising measure on generalized random graphs. We also give...     

Ising Models on Power-Law Random Graphs

We study a ferromagnetic Ising model on random graphs with a power-law degree distribution and compute the thermodynamic limit of the pressure when the mean degree is finite (degree exponent τ>2), for which the random graph has a tree-like structure. For this, we closely follow the analysis by Dembo and Montanari (Ann. Appl. Probab. 20(2):565–592, 2010) which assumes finite variance degrees (τ>3), adapting it when necessary and also simplifying it when possible. Our results also apply in cases where the degree distribution does not obey a power law.     

Mean-Field Analysis of the q-Voter Model on Networks

We present a detailed investigation of the behavior of the nonlinear q-voter model for opinion dynamics. At the mean-field level we derive analytically, for any value of the number q of agents involved in the elementary update, the phase diagram, the exit probability and the consensus time at the transition point. The mean-field formalism is extended to the case that the interaction pattern is given by generic heterogeneous networks. We finally discuss the case of random regular networks and compare analytical results with simulations.     

Existence of the Harmonic Measure for Random Walks on Graphs and in Random Environments

We give a sufficient condition for the existence of the harmonic measure from infinity of transient random walks on weighted graphs. In particular, this condition is verified by the random conductance model on ? ^d , d≥3, when the conductances are i.i.d. and the bonds with positive conductance percolate. The harmonic measure from infinity also exists for random walks on supercritical clusters of ?². This is proved using results of Barlow (Ann. Probab. 32:3024–3084, 2004) and Barlow and Hambly (Electron. J. Probab. 14(1):1–27, 2009).