Minimum-Weight Path in a Sparse Erdős--Rényi Graph with Signed Weights
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908679295467520 |
|---|---|
| author | Ma, Heng Maillard, Pascal |
| author_facet | Ma, Heng Maillard, Pascal |
| contents | We consider a sparse Erdős--Rényi graph $\mathcal{G}(n,λ/n)$ where each edge is independently assigned a random signed weight. For two uniformly chosen vertices, we study the joint distribution of the total weights and hopcounts (number of edges) of the near-minimum weight paths connecting them. Under certain conditions on the weight distribution, which ensure in particular that these paths are typically of positive weight, we prove that the point process formed by the rescaled pairs of total weight and hopcount, converges weakly to a Poisson point process with a random intensity. This random intensity is characterized by the product of two independent copies of the Biggins martingale limit of certain branching random walk. This result generalizes the work of Daly, Schulte, and Shneer (arXiv:2308.12149) from non-negative to signed weights. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22454 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimum-Weight Path in a Sparse Erdős--Rényi Graph with Signed Weights Ma, Heng Maillard, Pascal Probability We consider a sparse Erdős--Rényi graph $\mathcal{G}(n,λ/n)$ where each edge is independently assigned a random signed weight. For two uniformly chosen vertices, we study the joint distribution of the total weights and hopcounts (number of edges) of the near-minimum weight paths connecting them. Under certain conditions on the weight distribution, which ensure in particular that these paths are typically of positive weight, we prove that the point process formed by the rescaled pairs of total weight and hopcount, converges weakly to a Poisson point process with a random intensity. This random intensity is characterized by the product of two independent copies of the Biggins martingale limit of certain branching random walk. This result generalizes the work of Daly, Schulte, and Shneer (arXiv:2308.12149) from non-negative to signed weights. |
| title | Minimum-Weight Path in a Sparse Erdős--Rényi Graph with Signed Weights |
| topic | Probability |
| url | https://arxiv.org/abs/2511.22454 |