Moderate Deviations for the Size of the Largest Component in a Super-critical Erdos - Renyi Graph

J. Ameskamp, M. Lowe

2011, v.17, №3, 369-390


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


Please log in or register to leave a comment

There are no comments yet