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.
Funding
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