First passage percolation on Erdős-Rényi graphs with general weights
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918218424123392 |
|---|---|
| author | Daly, Fraser Schulte, Matthias Shneer, Seva |
| author_facet | Daly, Fraser Schulte, Matthias Shneer, Seva |
| contents | We consider first passage percolation on the Erdős--Rényi graph with $n$ vertices in which each pair of distinct vertices is connected independently by an edge with probability $λ/n$ for some $λ>1$. The edges of the graph are given non-negative i.i.d. weights with a non-degenerate distribution such that the probability of zero is not too large. We consider the paths with small total weight between two distinct typical vertices and analyse the joint behaviour of the numbers of edges on such paths, the so-called hopcounts, and the total weights of these paths. For $n\to\infty$, we show that, after a suitable transformation, the pairs of hopcounts and total weights of these paths converge in distribution to a Cox process, i.e., a Poisson process with a random intensity measure. The random intensity measure is controlled by two independent random variables, whose distribution is the solution of a distributional fixed point equation and is related to branching processes. For non-arithmetic and arithmetic edge-weight distributions we observe different behaviour. In particular, we derive the limiting distribution for the minimal total weight and the corresponding hopcount(s). Our results generalise earlier work of Bhamidi, van der Hofstad and Hooghiemstra, who assume that edge weights have an absolutely continuous distribution. The main tool we employ is the method of moments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_12149 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | First passage percolation on Erdős-Rényi graphs with general weights Daly, Fraser Schulte, Matthias Shneer, Seva Probability 60F05, 05C80 (Primary) 60C05, 60G55 (Secondary) We consider first passage percolation on the Erdős--Rényi graph with $n$ vertices in which each pair of distinct vertices is connected independently by an edge with probability $λ/n$ for some $λ>1$. The edges of the graph are given non-negative i.i.d. weights with a non-degenerate distribution such that the probability of zero is not too large. We consider the paths with small total weight between two distinct typical vertices and analyse the joint behaviour of the numbers of edges on such paths, the so-called hopcounts, and the total weights of these paths. For $n\to\infty$, we show that, after a suitable transformation, the pairs of hopcounts and total weights of these paths converge in distribution to a Cox process, i.e., a Poisson process with a random intensity measure. The random intensity measure is controlled by two independent random variables, whose distribution is the solution of a distributional fixed point equation and is related to branching processes. For non-arithmetic and arithmetic edge-weight distributions we observe different behaviour. In particular, we derive the limiting distribution for the minimal total weight and the corresponding hopcount(s). Our results generalise earlier work of Bhamidi, van der Hofstad and Hooghiemstra, who assume that edge weights have an absolutely continuous distribution. The main tool we employ is the method of moments. |
| title | First passage percolation on Erdős-Rényi graphs with general weights |
| topic | Probability 60F05, 05C80 (Primary) 60C05, 60G55 (Secondary) |
| url | https://arxiv.org/abs/2308.12149 |