Abstract
We consider the near-critical Erdos-Rényi random graph G(n, p) and provide a new probabilistic proof of the fact that, when p is of the form p=p(n)=1/n+λ/n4/3 and A is large, {equation presented} where Cmax is the largest connected component of the graph. Our result allows A and λ to depend on n. While this result is already known, our proof relies only on conceptual and adaptable tools such as ballot theorems, whereas the existing proof relies on a combinatorial formula specific to Erdos-Rényi graphs, together with analytic estimates.
| Original language | English |
|---|---|
| Pages (from-to) | 840 - 869 |
| Number of pages | 30 |
| Journal | Combinatorics, Probability and Computing |
| Volume | 31 |
| Issue number | 5 |
| Early online date | 11 Feb 2022 |
| DOIs | |
| Publication status | Published - 30 Sept 2022 |
Bibliographical note
Funding Information:Both authors would like to thank Nathanaël Berestycki for some very helpful discussions. We also thank the Royal Society for their generous funding, of a PhD scholarship for UDA and a University Research Fellowship for MR. Finally, we thank two anonymous referees for their thoughtful comments and suggestions, which helped us to improve the paper.
Keywords
- ballot theorem
- Brownian Motion
- component size
- Random graph
- random walk
ASJC Scopus subject areas
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics