On the Asymptotics of the Connectivity Probability of Erdos-Renyi Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909575642349568 |
|---|---|
| author | Chinyaev, B. Shklyaev, A. |
| author_facet | Chinyaev, B. Shklyaev, A. |
| contents | In this paper, we investigate the exact asymptotic behavior of the connectivity probability in the Erdos-Renyi graph G(n,p), under different asymptotic assumptions on the edge probability p=p(n). We propose a novel approach based on the analysis of inhomogeneous random walks to derive this probability. We show that the problem of graph connectivity can be reduced to determining the probability that an inhomogeneous random walk with Poisson-distributed increments, conditioned to form a bridge, is actually an excursion |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_08576 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Asymptotics of the Connectivity Probability of Erdos-Renyi Graphs Chinyaev, B. Shklyaev, A. Probability Combinatorics In this paper, we investigate the exact asymptotic behavior of the connectivity probability in the Erdos-Renyi graph G(n,p), under different asymptotic assumptions on the edge probability p=p(n). We propose a novel approach based on the analysis of inhomogeneous random walks to derive this probability. We show that the problem of graph connectivity can be reduced to determining the probability that an inhomogeneous random walk with Poisson-distributed increments, conditioned to form a bridge, is actually an excursion |
| title | On the Asymptotics of the Connectivity Probability of Erdos-Renyi Graphs |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2504.08576 |