HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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
Long-term archiving on: : Thursday, April 7, 2022 - 7:25:00 PM

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

Record views

30

Files downloads

19