Foss, Sergey, Konstantopoulos, Takis and Pyatkin, Artem
(2023)
PROBABILISTIC AND ANALYTICAL PROPERTIES OF THE LAST PASSAGE PERCOLATION CONSTANT IN A WEIGHTED RANDOM DIRECTED GRAPH.
ANNALS OF APPLIED PROBABILITY, 33 (2).
pp. 731-753.
Abstract
To each edge (i, j), i < j, of the complete directed graph on the integers we assign unit weight with probability p or weight x with probability 1 − p, independently from edge to edge, and give to each path weight equal to the sum of its edge weights. If W0x,n is the maximum weight of all paths from 0 to n then W0x,n/n → Cp(x), as n → ∞, almost surely, where Cp(x) is positive and deterministic. We study Cp(x) as a function of x, for fixed 0 < p < 1, and show that it is a strictly increasing convex function that is not differentiable if and only if x is a nonpositive rational or a positive integer except 1 or the reciprocal of it. We allow x to be any real number, even negative, or, possibly, −∞. The case x = −∞ corresponds to the well-studied directed version of the Erdős–Rényi random graph (known as Barak–Erdős graph) for which Cp(−∞) = limx→−∞ Cp(x) has been studied as a function of p in a number of papers.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Random graph, maximal path, last-passage percolation, skeleton point, critical point, regenerative structure |
Divisions: | Faculty of Science and Engineering > School of Physical Sciences |
Depositing User: | Symplectic Admin |
Date Deposited: | 02 Oct 2023 14:55 |
Last Modified: | 17 Mar 2024 16:32 |
DOI: | 10.1214/22-AAP1832 |
Open Access URL: | https://arxiv.org/pdf/2006.01727.pdf |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3173311 |