Moderate Deviations for the Size of the Largest Component in a Super-critical Erdos - Renyi Graph
J. Ameskamp, M. Lowe
2011, v.17, Issue 3, 369-390
ABSTRACT
We study the size of the largest component of a supercritical Erdos - Renyi graph $\G(n,p)$, in the regime where $p=\lambda/n$ and $\lambda >1$. It is well known that the largest component is of order $\zeta_\lambda n$ where $\zeta_\l$ is the extinction probability of a supercritical Galton - Watson process. We prove a Moderate Deviation Principle for the size of the largest component around this value, thus closing the gap between the Central Limit Theorem and a Large Deviation Principle.
Keywords: moderate deviations,random graphs,large deviations,limittheorems
COMMENTS
Please log in or register to leave a comment