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

Abstract

We consider an inhomogeneous version of the Barak-Erdős graph, i.e. a directed Erős-Rényi random graph on $\{1,\dots ,n\}$ with no loop. Given $f$ a Riemann-integrable non-negative function on $[0,1{]}^2$ and $\gamma >0$, we define $G(n,f,\gamma )$ as the random graph with vertex set $\{1,\dots ,n\}$ such that for each $i<j$ the directed edge $(i,j)$ is present with probability $p_{i,j}^{(n)}=\frac{f(i/n,j/n)}{n^{\gamma }}$, independently of any other edge. We denote by $L_n$ the length of the shortest path between vertices $1$ and $n$, and take interest in the asymptotic behaviour of $L_n$ as $n\to \infty$.