




















We study the near-critical behavior of the sparse Erdős-Rényi random graph $\mathcal{G}(n,p)$ on $n\gg1$ vertices, where the connection probability $p$ satisfies $np = 1+θ(b_n^2/n)^{1/3}$, with $n^{3/10}\ll {b_n}\ll n^{1/2}$, and $θ\in\mathbb{R}$. To this end, we introduce an empirical measure that describes connected components of $\mathcal{G}(n,p)$ of mesoscopic size $\propto (nb_n)^{2/3}$, and we characterize its large deviation behavior. The proof hinges on detailed combinatorial estimates and optimization procedures. In particular, we give precise estimates for the probability that the graph has no connected component of mesoscopic size or larger. We argue that these are a stepping stone for the analysis of more general inhomogeneous random graphs. Our proof strategy gives new and accurate estimates of the probability that the sparse Erdős-Rényi graph is connected.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。