Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

On the length of the shortest path in a sparse Barak-Erd\H{o}s graph

Abstract : We consider an inhomogeneous version of the Barak-Erd\H{o}s graph, i.e. a directed Er\H{o}s-R\'enyi random graph on $\{1,\ldots,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,\ldots,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$.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03514819
Contributor : Bastien Mallein Connect in order to contact the contributor
Submitted on : Thursday, January 6, 2022 - 2:22:42 PM
Last modification on : Thursday, January 13, 2022 - 4:12:24 AM

File

shortestPathRemarkSteinComplet...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03514819, version 1
  • ARXIV : 2112.14932

Citation

Bastien Mallein, Pavel Tesemnikov. On the length of the shortest path in a sparse Barak-Erd\H{o}s graph. 2022. ⟨hal-03514819⟩

Share

Metrics

Les métriques sont temporairement indisponibles