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

A Barak-Erdős digraph is a random subgraph of a transitive tournament. Usually, the digraph is defined in the vertex set \(\{1, \dotsc, n\}\), and for every \(i < j\), including the directed edge of the form \((i,j)\) independently, with the same probability each. Here, the authors consider instead a space-inhomogenous version of the Barak-Erdős digraph, akin to the inhomogeneous random graphs sampled from graphons [\textit{L. Lovász} and \textit{B. Szegedy}, J. Comb. Theory, Ser. B 96, No. 6, 933--957 (2006; Zbl 1113.05092)]. More precisely, the authors consider a Riemann-integrable positive function in \([0,1]^2\) and \(\gamma \in (0,1)\), and a random digraph \(G(n, f, \gamma)\) defined by including, for every \(i < j\), the directed edge \((i,j)\) with probability \(p^{(n)}_{i,j} = f(i/n, j/n)/n^{\gamma}\), independently. The authors investigate the parameter \(L_n\) in \(G(n, f, \gamma)\), which is the length of the shortest directed path between \(1\) and \(n\) in \(G(n, f, \gamma)\). This parameter was considered before in the homogeneous setting [\textit{P. I. Tesemnikov}, Sib. Èlektron. Mat. Izv. 15, 1556--1565 (2018; Zbl 1411.05236)], and the analysis here recovers some of the results obtained before. In summary, \(L_n\) can be shown to be at least \(1/(1 - \gamma)\) with probability tending to \(1\), and the probability of \(L_n = 1/(1 - \gamma)\) is shown to converge to an explicit constant depending on \(f\). The proofs are short and use standard techniques, e.g. the Chen-Stein method.