Considering an Erdos Renyi random graph with $p = \frac{\lambda}{n}$ and $\lambda < 1$, I am trying to show that $ \frac{|C_{max}|}{log (n)} $ approaches $ \frac{1}{I_{\lambda}} $ in probability, where $|C_{max}|$ is the size of the largest component and $I_\lambda = \lambda -1 – log(\lambda)$.
So I should show that:
$$ \lim_{n \to \infty} P(|\frac{|C_{max}|}{log (n)} – \frac{1}{I_{\lambda}}| > \epsilon) = 0 $$
I think I should use the upper and lower bounds on the largest subcritical component, i.e. $P(|C_{max}|\ge a log(n)) = O(n^{-\delta})$ if $ a > \frac{1}{I_\lambda} $ and $P(|C_{max}|\le a log(n)) = O(n^{-\delta})$ if $ a < \frac{1}{I_\lambda} $, which means that $|C_{max}| \approx \frac{1}{I_\lambda}log(n)$. Then rewriting the equation above:
$$ \lim_{n \to \infty} P(||C_{max}| – \frac{1}{I_{\lambda}} log (n)| > \epsilon log (n)) = 0 $$
Then I should be able to use Chebyshev's inequality, but I'm not sure if this approach is valid until now and I don't know what the variance of $|C_{max}|$ is.
Best Answer
So you're not interested in proving those upper and lower bounds, just in using them to prove convergence in probability?
For that, you don't need any extra knowledge of the random graph. For any $\epsilon>0$, the first bound says that we have $$ \Pr[|C_{\max} > (\tfrac1{I_\lambda} + \epsilon)\log n] = O(n^{-\delta}) $$ (presumably for some $\delta>0$ depending on $\epsilon$) which we can rewrite as $$ \Pr\left[\frac{C_{\max}}{\log n} - \frac1{I_\lambda} > \epsilon\right] = O(n^{-\delta}) $$ and this goes to $0$ in the limit as $n \to \infty$. Similarly, the second bound tells us that $$ \Pr[|C_{\max}| < (\tfrac1{I_\lambda} - \epsilon)\log n] = O(n^{-\delta}) $$ and this can be rewritten as $$ \Pr\left[\frac{C_{\max}}{\log n} - \frac1{I_\lambda} < -\epsilon\right] = O(n^{-\delta}) $$ which also goes to $0$ in the limit as $n \to \infty$. Finally, the probability you were looking for, $$ \Pr\left[\left|\frac{C_{\max}}{\log n} -\frac1{I_\lambda}\right| > \epsilon\right], $$ is the sum of the two probabilities above, so its limit is also $0$.