TY - JOUR

T1 - On the length of the shortest path in a sparse Barak–Erdős graph

AU - Mallein, Bastien

AU - Tesemnikov, Pavel

N1 - Funding Information: The research of both authors was supported by joint grant ( 19-51-15001 ) of the Russian Foundation for Basic Research and from the French CNRS ’ PRC grant. Publisher Copyright: © 2022 Elsevier B.V.

PY - 2022/11

Y1 - 2022/11

N2 - We consider an inhomogeneous version of the Barak–Erdős graph, i.e. a directed Erdős–Rényi random graph on {1,…,n} with no loop. Given f a Riemann-integrable non-negative function on [0,1]2 and γ>0, we define G(n,f,γ) as the random graph with vertex set {1,…,n} such that for each ii,j(n)=[Formula presented], independently of any other edge. We denote by Ln the length of the shortest path between vertices 1 and n, and take interest in the asymptotic behaviour of Ln as n→∞.

AB - We consider an inhomogeneous version of the Barak–Erdős graph, i.e. a directed Erdős–Rényi random graph on {1,…,n} with no loop. Given f a Riemann-integrable non-negative function on [0,1]2 and γ>0, we define G(n,f,γ) as the random graph with vertex set {1,…,n} such that for each ii,j(n)=[Formula presented], independently of any other edge. We denote by Ln the length of the shortest path between vertices 1 and n, and take interest in the asymptotic behaviour of Ln as n→∞.

KW - Chain length

KW - Chen–Stein method

KW - Directed Erdos–Renyi graph

KW - Food chain

KW - Parallel processing

KW - Random directed graph

UR - http://www.scopus.com/inward/record.url?scp=85136268589&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/a20cb0e3-18f5-3319-9ed5-8f84b7f2be8b/

U2 - 10.1016/j.spl.2022.109634

DO - 10.1016/j.spl.2022.109634

M3 - Article

AN - SCOPUS:85136268589

VL - 190

JO - Statistics and Probability Letters

JF - Statistics and Probability Letters

SN - 0167-7152

M1 - 109634

ER -