Search

We study a geometric version of first-passage percolation on the complete graph, known as long-range first-passage percolation. Here, the vertices of the complete graph K n are embedded in the d-dimensional torus T n d , and each edge e is assigned an independent transmission time T e = ‖ e ‖ T n d α E e , where E e is a rate-one exponential random variable associated with the edge e, ‖ · ‖ T n d denotes the torus-norm, and α ≥ 0 is a parameter. We are interested in the case α ∈ [ 0 , d) , which corresponds to the instantaneous percolation regime for long-range first-passage percolation on Z d studied by Chatterjee and Dey [14], and which extends first-passage percolation on the complete graph (the α = 0 case) studied by Janson [24]. We consider the typical distance, flooding time, and diameter of the model. Our results show a 1, 2, 3-type result, akin to first-passage percolation on the complete graph as shown by Janson. The results also provide a quantitative perspective to the qualitative results observed by Chatterjee and Dey on Z d . [ABSTRACT FROM AUTHOR]

We study competing first passage percolation on graphs generated by the configuration model with infinite-mean degrees. Initially, two uniformly chosen vertices are infected with a type 1 and type 2 infection, respectively, and the infection then spreads via nearest neighbors in the graph. The time it takes for the type 1 (resp. 2) infection to traverse an edge e is given by a random variable $X_1(e)$ (resp. $X_2(e)$) and, if the vertex at the other end of the edge is still uninfected, it then becomes type 1 (resp. 2) infected and immune to the other type. Assuming that the degrees follow a power-law distribution with exponent $\tau \in (1,2)$ , we show that with high probability as the number of vertices tends to infinity, one of the infection types occupies all vertices except for the starting point of the other type. Moreover, both infections have a positive probability of winning regardless of the passage-time distribution. The result is also shown to hold for the erased configuration model, where self-loops are erased and multiple edges are merged, and when the degrees are conditioned to be smaller than $n^\alpha$ for some $\alpha\gt 0$. [ABSTRACT FROM AUTHOR]

We study the random geometry of first passage percolation on the complete graph equipped with independent and identically distributed positive edge weights. We consider the case where the lower extreme values of the edge weights are highly separated. This model exhibits strong disorder and a crossover between local and global scales. Local neighborhoods are related to invasion percolation that display self-organised criticality. Globally, the edges with relevant edge weights form a barely supercritical Erdős–Rényi random graph that can be described by branching processes. This near-critical behaviour gives rise to optimal paths that are considerably longer than logarithmic in the number of vertices, interpolating between random graph and minimal spanning tree path lengths. Crucial to our approach is the quantification of the extreme-value behavior of small edge weights in terms of a sequence of parameters (s n) n ≥ 1 that characterises the different universality classes for first passage percolation on the complete graph. We investigate the case where s n → ∞ with s n = o (n 1 / 3) , which corresponds to the barely supercritical setting. We identify the scaling limit of the weight of the optimal path between two vertices, and we prove that the number of edges in this path obeys a central limit theorem with mean approximately s n log (n / s n 3) and variance s n 2 log (n / s n 3) . Remarkably, our proof also applies to n-dependent edge weights of the form E s n , where E is an exponential random variable with mean 1, thus settling a conjecture of Bhamidi et al. (Weak disorder asymptotics in the stochastic meanfield model of distance. Ann Appl Probab 22(1):29–69, 2012). The proof relies on a decomposition of the smallest-weight tree into an initial part following invasion percolation dynamics, and a main part following branching process dynamics. The initial part has been studied in Eckhoff et al. (Long paths in first passage percolation on the complete graph I. Local PWIT dynamics. Electron. J. Probab. 25:1–45, 2020. 10.1214/20-EJP484); the current paper focuses on the global branching dynamics. [ABSTRACT FROM AUTHOR]

We prove results for first-passage percolation on the configuration model with degrees having asymptotic finite mean, infinite variance and i.i.d. edge-weights with strictly positive support of the form Y=a+X, where a is a positive constant and the excess edge-weight X is a non-negative random variable with zero as the infimum of its support. We prove that the weight of the optimal path between two uniformly chosen vertices has tight fluctuations around the asymptotic mean of the graph-distance if and only if the following condition holds: the random variable X is such that the age-dependent branching process describing first-passage percolation exploration in the same graph with edge-weights from distribution X has a positive probability to reach infinitely many individuals in a finite time. This shows that almost-shortest paths in the graph-distance proliferate, in the sense that there even exist paths having tight total excess edge-weight for appropriate edge-weight distributions. Our proof makes use of a degree-dependent percolation model that we believe is interesting in its own right, as well as tightness results for distances in scale-free configuration models that we prove to hold under rather weak conditions on the degrees. [ABSTRACT FROM AUTHOR]

We formulate and study a model for inhomogeneous long-range percolation on ℤd. Each vertex x ϵ ℤd is assigned a non-negative weight Wx, where (Wx)xϵℤd are i.i.d. random variables. Conditionally on the weights, and given two parameters a, A > 0, the edges are independent and the probability that there is an edge between x and y is given by Pxy = 1 - exp{ -λWx Wy / ∣x - y ∣α}. The parameter λ is the percolation parameter, while a describes the long-range nature of the model. We focus on the degree distribution in the resulting graph, on whether there exists an infinite component and on graph distance between remote pairs of vertices. First, we show that the tail behavior of the degree distribution is related to the tail behavior of the weight distribution. When the tail of the distribution of Wx is regularly varying with exponent τ - 1, then the tail of the degree distribution is regularly varying with exponent γ = α(τ - l)/d. The parameter γ turns out to be crucial for the behavior of the model. Conditions on the weight distribution and γ are formulated for the existence of a critical value λ c ϵ(0, ∞) such that the graph contains an infinite component when λ > λc and no infinite component when λ < λc. Furthermore, a phase transition is established for the graph distances between vertices in the infinite component at the point γ = 2, that is, at the point where the degrees switch from having finite to infinite second moment. The model can be viewed as an interpolation between long-range percolation and models for inhomogeneous random graphs, and we show that the behavior shares the interesting features of both these models. [ABSTRACT FROM AUTHOR]

Abstract: Let be a d-dimensional random walk in random scenery, i.e., with a random walk in and an i.i.d. scenery, independent of the walk. We assume that the random variables have a stretched exponential tail. In particular, they do not possess exponential moments. We identify the speed and the rate of the logarithmic decay of for all sequences satisfying a certain lower bound. This complements results of Gantert et al. [Annealed deviations of random walk in random scenery, preprint, 2005], where it was assumed that has exponential moments of all orders. In contrast to the situation (Gantert et al., 2005), the event is not realized by a homogeneous behavior of the walk''s local times and the scenery, but by many visits of the walker to a particular site and a large value of the scenery at that site. This reflects a well-known extreme behavior typical for random variables having no exponential moments. [Copyright &y& Elsevier]