Search

We study first-passage percolation on random simple triangulations and their dual maps with independent identically distributed link weights. Our main result shows that the first-passage percolation distance concentrates in an op(n1/4) window around a constant multiple of the graph distance. Our approach follows the proof strategy by Curien and Le Gall (Ann. Sci. Éc. Norm. Supér., 2019), but we have to overcome several obstacles specific to simple triangulations. [ABSTRACT FROM AUTHOR]

Simple heuristics for (combinatorial) optimization problems often show a remarkable performance in practice. Worst-case analysis often falls short of explaining this performance. Because of this, "beyond worst-case analysis" of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms. The instances of many (combinatorial) optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained in recent years, where random shortest path metrics generated from dense graphs (either complete graphs or Erdős–Rényi random graphs) have been used so far. In this paper we extend these findings to sparse graphs, with a focus on sparse graphs with 'fast growing cut sizes', i.e. graphs for which | δ (U) | = Ω (| U | ε) for some constant ε ∈ (0 , 1) for all subsets U of the vertices, where δ (U) is the set of edges connecting U to the remaining vertices. A random shortest path metric is constructed by drawing independent random edge weights for each edge in the graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For such instances generated from a sparse graph with fast growing cut sizes, we prove that the greedy heuristic for the minimum distance maximum matching problem, and the nearest neighbor and insertion heuristics for the traveling salesman problem all achieve a constant expected approximation ratio. Additionally, for instances generated from an arbitrary sparse graph, we show that the 2-opt heuristic for the traveling salesman problem also achieves a constant expected approximation ratio. [ABSTRACT FROM AUTHOR]

The Eden cell growth model is a simple discrete stochastic process which produces a "blob" (aggregation of cells) in R d : start with one cube in the regular grid, and at each time step add a neighboring cube uniformly at random. This process has been used as a model for the growth of aggregations, tumors, and bacterial colonies and the healing of wounds, among other natural processes. Here, we study the topology and local geometry of the resulting structure, establishing asymptotic bounds for Betti numbers. Our main result is that the Betti numbers at time t grow at a rate between t (d - 1) / d and P d (t) , where P d (t) is the size of the site perimeter. Assuming a widely believed conjecture, this establishes the rate of growth of the Betti numbers in every dimension. We also present the results of computational experiments on finer aspects of the geometry and topology, such as persistent homology and the distribution of shapes of holes. [ABSTRACT FROM AUTHOR]

We consider Bernoulli first-passage percolation on the [Formula: see text]-dimensional hypercubic lattice with [Formula: see text]. The passage time of edge [Formula: see text] is 0 with probability [Formula: see text] and 1 with probability [Formula: see text], independently of each other. Let [Formula: see text] be the critical probability for percolation of edges with passage time 0. When [Formula: see text], there exists a nonrandom, nonempty compact convex set [Formula: see text] such that the set of vertices to which the first-passage time from the origin is within [Formula: see text] is well approximated by [Formula: see text] for all large [Formula: see text], with probability one. The aim of this paper is to prove that for [Formula: see text], the Hausdorff distance between [Formula: see text] and [Formula: see text] grows linearly in [Formula: see text]. Moreover, we mention that the approach taken in the paper provides a lower bound for the expected size of the intersection of geodesics, that gives a nontrivial consequence for the critical case.

We obtain quantitative stochastic homogenization results for Hamilton–Jacobi equations arising in front propagation problems which move in the normal direction with a possible unbounded velocity. More precisely, we establish error estimates and rates of convergence for homogenization and effective Hamiltonian. The main idea is to perturb our unbounded problem by a bounded one, and to establish stability results in this context. Then, we combine the estimates that we find with the ones from the bounded case. [ABSTRACT FROM AUTHOR]

Simple heuristics often show a remarkable performance in practice for optimization problems. Worst-case analysis often falls short of explaining this performance. Because of this, "beyond worst-case analysis" of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms. The instances of many optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained by Bringmann et al. (Algorithmica , 2013), who have used random shortest path metrics constructed using complete graphs to analyze heuristics. The goal of this paper is to generalize these findings to non-complete graphs, especially Erdős–Rényi random graphs. A random shortest path metric is constructed by drawing independent random edge weights for each edge in the graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For such instances, we prove that the greedy heuristic for the minimum distance maximum matching problem, the nearest neighbor and insertion heuristics for the traveling salesman problem, and a trivial heuristic for the k -median problem all achieve a constant expected approximation ratio. Additionally, we show a polynomial upper bound for the expected number of iterations of the 2-opt heuristic for the traveling salesman problem. [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]

The Euclidean first-passage percolation model of Howard and Newman is a rotationally invariant percolation model built on a Poisson point process. It is known that the passage time between 0 and n e 1 obeys a diffusive upper bound: Var T (0 , n e 1) ≤ C n , and in this paper we improve this inequality to C n ∕ log n. The methods follow the strategy used for sublinear variance proofs on the lattice, using the Falik–Samorodnitsky inequality and a Bernoulli encoding, but with substantial technical difficulties. To deal with the different setup of the Euclidean model, we represent the passage time as a function of Bernoulli sequences and uniform sequences, and develop several "greedy lattice animal" arguments. [ABSTRACT FROM AUTHOR]

We consider translation invariant measures on families of nearest-neighbor semi-infinite walks on the integer lattice. We assume that once walks meet, they coalesce. In 2d, we classify the collective behavior of these walks under mild assumptions: they either coalesce almost surely or form bi-infinite trajectories. Bi-infinite trajectories form measure-preserving dynamical systems, have a common asymptotic direction in 2d, and possess other nice properties. We use our theory to classify the behavior of compatible families of semi-infinite geodesics in stationary first- and last-passage percolation. We also partially answer a question raised by C. Hoffman about the limiting empirical measure of weights seen by geodesics. We construct several examples: our main example is a standard first-passage percolation model where geodesics coalesce almost surely, but have no asymptotic direction or average weight. [ABSTRACT FROM AUTHOR]

We study the height of a spanning tree T of a graph G obtained by starting with a single vertex of G and repeatedly selecting, uniformly at random, an edge of G with exactly one endpoint in T and adding this edge to T. [ABSTRACT FROM AUTHOR]

Consider (independent) first-passage percolation on the sites of the triangular lattice T embedded in C . Denote the passage time of the site v in T by t ( v ) , and assume that P ( t ( v ) = 0 ) = P ( t ( v ) = 1 ) = 1 ∕ 2 . Denote by b 0 , n the passage time from 0 to the halfplane { v ∈ T : Re ( v ) ≥ n } , and by T ( 0 , n u ) the passage time from 0 to the nearest site to n u , where | u | = 1 . We prove that as n → ∞ , b 0 , n ∕ log n → 1 ∕ ( 2 3 π ) a.s., E [ b 0 , n ] ∕ log n → 1 ∕ ( 2 3 π ) and Var [ b 0 , n ] ∕ log n → 2 ∕ ( 3 3 π ) − 1 ∕ ( 2 π 2 ) ; T ( 0 , n u ) ∕ log n → 1 ∕ ( 3 π ) in probability but not a.s., E [ T ( 0 , n u ) ] ∕ log n → 1 ∕ ( 3 π ) and Var [ T ( 0 , n u ) ] ∕ log n → 4 ∕ ( 3 3 π ) − 1 ∕ π 2 . This answers a question of Kesten and Zhang (1997) and improves our previous work (2014). From this result, we derive an explicit form of the central limit theorem for b 0 , n and T ( 0 , n u ) . A key ingredient for the proof is the moment generating function of the conformal radii for conformal loop ensemble CLE 6 , given by Schramm et al. (2009). [ABSTRACT FROM AUTHOR]

The article focuses on the flooding time problem and rumor propagation on graphs. Topics include the comparison of ratio between the expected propagation time for all pieces of information and corresponding time for a single piece of information, the first passage percolation on a graph, the total propagation time on graphs.

We prove nonuniversality results for first-passage percolation on the configuration model with independent and identically distributed (i.i.d.) degrees having infinite variance. We focus on the weight of the optimal path between two uniform vertices. Depending on the properties of the weight distribution, we use an example-based approach and show that rather different behaviours are possible. When the weights are almost surely larger than a constant, the weight and number of edges in the graph grow proportionally to log log n, as for the graph distances. On the other hand, when the continuous-time branching process describing the first-passage percolation exploration through the graph reaches infinitely many vertices in finite time, the weight converges to the sum of two i.i.d. random variables representing the explosion times of the continuous-time processes started from the two sources. This nonuniversality is in sharp contrast to the setting where the degree sequence has a finite variance, Bhamidi et al. (2012). [ABSTRACT FROM AUTHOR]

We consider first-passage percolation on the d dimensional cubic lattice for d ≥ 2 ; that is, we assign independently to each edge e a nonnegative random weight t e with a common distribution and consider the induced random graph distance (the passage time), T ( x , y ) . It is known that for each x ∈ Z d , μ ( x ) = lim n T ( 0 , n x ) / n exists and that 0 ≤ E T ( 0 , x ) − μ ( x ) ≤ C ‖ x ‖ 1 1 / 2 log ‖ x ‖ 1 under the condition E e α t e < ∞ for some α > 0 . By combining tools from concentration of measure with Alexander’s methods, we show how such bounds can be extended to t e ’s with distributions that have only low moments. For such edge-weights, we obtain an improved bound C ( ‖ x ‖ 1 log ‖ x ‖ 1 ) 1 / 2 and bounds on the rate of convergence to the limit shape. [ABSTRACT FROM AUTHOR]

We consider first-passage percolation on segment processes and provide concentration results concerning moderate deviations of shortest-path lengths from a linear function in the distance of their endpoints. The proofs are based on a martingale technique developed by [H. Kesten, Ann. Appl. Probab. 3 (1993) 296-338.] for an analogous problem on the lattice. Our results are applicable to graph models from stochastic geometry. For example, they imply that the time constant in Poisson-Voronoi and Poisson-Delaunay tessellations is strictly greater than 1. Furthermore, applying the framework of Howard and Newman, our results can be used to study the geometry of geodesics in planar shortest-path trees. [ABSTRACT FROM AUTHOR]

For sub-additive ergodic processes { X m , n } with weak dependence, we analyze the rate of convergence of E X 0 , n / n to its limit g . We define an exponent γ given roughly by E X 0 , n ∼ n g + n γ , and, assuming existence of a fluctuation exponent χ that gives Var X 0 , n ∼ n 2 χ , we provide a lower bound for γ of the form γ ≥ χ . The main requirement is that χ ≠ 1 / 2 . In the case χ = 1 / 2 and under the assumption Var X 0 , n = O ( n / ( log ⁡ n ) β ) for some β > 0 , we prove γ ≥ χ − c ( β ) for a β -dependent constant c ( β ) . These results show in particular that non-diffusive fluctuations are associated to non-trivial γ . Various models, including first-passage percolation, directed polymers, the minimum of a branching random walk and bin packing, fall into our general framework, and the results apply assuming χ exists. In the case of first-passage percolation in Z d , we provide a version of γ ≥ − 1 / 2 without assuming existence of χ . [ABSTRACT FROM AUTHOR]

This paper discusses a simple stochastic model for the spread of messages in a large population with two types of individuals: transmitters and receivers. Transmitters, after receiving the message, start spreading copies of the message to their neighbors. Receivers may receive the message but will never spread it further. We derive approximations of the broadcast time and the first passage times of selected individuals in populations of size tending to infinity. These approximations explain how much the fact that only a fraction of the individuals are transmitters slows down the propagation of information. Our results also sharply characterize the statistical dependence structure of first passage times using Gumbel and logistic distributions of extreme value statistics. [ABSTRACT FROM AUTHOR]

We prove explicit estimates for the error in random homogenization of degenerate, second-order Hamilton-Jacobi equations, assuming the coefficients satisfy a finite range of dependence. In particular, we obtain an algebraic rate of convergence with overwhelming probability under certain structural conditions on the Hamiltonian. [ABSTRACT FROM AUTHOR]

In this paper we consider first-passage percolation on certain one-dimensional periodic graphs, such as the ℤ x {0, 1,..., K - 1}d - 1 nearest neighbour graph for d, K ≥ 1. We expose a regenerative structure within the first-passage process, and use this structure to show that both length and weight of minimal-weight paths present a typical one-dimensional asymptotic behaviour. Apart from a strong law of large numbers, we derive a central limit theorem, a law of the iterated logarithm, and a Donsker theorem for these quantities. In addition, we prove that the mean and variance of the length and weight of minimizing paths are monotone in the distance between their end-points, and further show how the regenerative idea can be used to couple two first-passage processes to eventually coincide. Using this coupling we derive a 0-1 law. [ABSTRACT FROM AUTHOR]

In first-passage percolation on the integer lattice, the shape theorem provides precise conditions for convergence of the set of sites reachable within a given time from the origin, once rescaled, to a compact and convex limiting shape. Here, we address convergence towards an asymptotic shape for cone-like subgraphs of the $${\mathbb {Z}}^d$$ lattice, where $$d\ge 2$$ . In particular, we identify the asymptotic shapes associated with these graphs as restrictions of the asymptotic shape of the lattice. Apart from providing necessary and sufficient conditions for $$L^p$$ - and almost sure convergence towards this shape, we investigate also stronger notions such as complete convergence and stability with respect to a dynamically evolving environment. [ABSTRACT FROM AUTHOR]

The article discusses a study presenting the first quantitative homogenization results for Hamilton-Jacobi equations in the stochastic setting. It assumes that the Hamiltonian H = H (p,y,w) satisfies a finite range dependence hypothesis in its spatial dependence. Its arguments rely on adaptations of some of the probabilistic techniques based on Azuma's inequality and the martingale method of bounded differences and do not yield sharp error estimates or convergence rates for homogenization.

We consider standard first-passage percolation on ℤd. Let e1 be the first coordinate vector. Let a(n) be the expected passage time from the origin to ne1. In this short paper, we note that a(n) is increasing under some strong condition on the support of the distribution of the passage times on the edges. [ABSTRACT FROM AUTHOR]

We prove that first-passage percolation times across thin cylinders of the form [0, n] × [− h, h] obey Gaussian central limit theorems as long as h grows slower than n. It is an open question as to what is the fastest that h can grow so that a Gaussian CLT still holds. Under the natural but unproven assumption about existence of fluctuation and transversal exponents, and strict convexity of the limiting shape in the direction of (1, 0, . . . , 0), we prove that in dimensions 2 and 3 the CLT holds all the way up to the height of the unrestricted geodesic. We also provide some numerical evidence in support of the conjecture in dimension 2. [ABSTRACT FROM AUTHOR]

We study first-passage percolation in two dimensions, using measures μ on passage times with b: = inf supp( μ) > 0 and $${\mu(\{b\})=p\geq \vec p_c}$$ , the threshold for oriented percolation. We first show that for each such μ, the boundary of the limit shape for μ is differentiable at the endpoints of flat edges in the so-called percolation cone. We then conclude that the limit shape must be non-polygonal for all of these measures. Furthermore, the associated Richardson-type growth model admits infinite coexistence and if μ is not purely atomic the graph of infection has infinitely many ends. We go on to show that lower bounds for fluctuations of the passage time given by Newman-Piza extend to these measures. We establish a lower bound for the variance of the passage time to distance n of order log n in any direction outside the percolation cone under a condition of finite exponential moments for μ. This result confirms a prediction of Newman and Piza (Ann Probab 23:977-1005, ) and Zhang (Ann Probab 36:331-362, ). Under the assumption of finite radius of curvature for the limit shape in these directions, we obtain a power-law lower bound for the variance and an inequality between the exponents χ and ξ. [ABSTRACT FROM AUTHOR]

We study the asymptotic behavior of dilute spin lattice energies by exhibiting a continuous interfacial limit energy computed using the notion of Γ-convergence and techniques mixing Geometric Measure Theory and Percolation while scaling to zero the lattice spacing. The limit is not trivial above a percolation threshold. Since the lattice energies are not equi-coercive, a suitable notion of limit magnetization must be defined, which can be characterized by two phases separated by an interface. The macroscopic surface tension at this interface is characterized through a first-passage percolation formula, which highlights interesting connections between variational problems and percolation issues. A companion result on the asymptotic description on energies defined on paths in a dilute environment is also given. [ABSTRACT FROM AUTHOR]

We consider a model of queues in discrete time, with batch services and arrivals. The case where arrival and service batches both have Bernoulli distributions corresponds to a discrete-time M/ M/1 queue, and the case where both have geometric distributions has also been previously studied. We describe a common extension to a more general class where the batches are the product of a Bernoulli and a geometric, and use reversibility arguments to prove versions of Burke’s theorem for these models. Extensions to models with continuous time or continuous workload are also described. As an application, we show how these results can be combined with methods of Seppäläinen and O’Connell to provide exact solutions for a new class of first-passage percolation problems. [ABSTRACT FROM AUTHOR]

In ballistic deposition (BD), ( d+1)-dimensional particles fall sequentially at random towards an initially flat, large but bounded d-dimensional surface, and each particle sticks to the first point of contact. For both lattice and continuum BD, a law of large numbers in the thermodynamic limit establishes convergence of the mean height and surface width (sample standard deviation of the height) of the interface to constants h( t) and w( t), respectively, depending on time t. We show that h( t) is asymptotically linear in t, while ( w( t))2 grows at least logarithmically in t when d=1. We use duality results showing that w( t) can be interpreted as the standard deviation of the height for deposition onto a surface growing from a single point. [ABSTRACT FROM AUTHOR]

Abstract: We consider the standard first-passage percolation in for and we denote by the maximal flow through the cylinder from its bottom to its top. Kesten proved a law of large numbers for the maximal flow in dimension 3: under some assumptions, converges towards a constant . We look now at the probability that is greater than for some , and we show under some assumptions that this probability decays exponentially fast with the volume of the cylinder. Moreover, we prove a large deviation principle for the sequence . [Copyright &y& Elsevier]

Abstract: We construct a probabilistic model which “mimics” the behaviour of a certain number-theoretical algorithm. This model involves study of a binary tree with randomly labelled edges, such that the labels have different distributions, depending on their directions. A number of properties of this tree are rigorously studied. As an application, this study could suggest what one could expect in the original algorithm. [Copyright &y& Elsevier]

We consider a sequence of random graphs constructed by a hierarchical procedure. The construction replaces existing edges by pairs of edges in series or parallel with probability p. We investigate the effective resistance across the graphs, first-passage percolation on the graphs and the Cheeger constants of the graphs as the number of edges tends to infinity. In each case we find a phase transition at p = ½. [ABSTRACT FROM AUTHOR]