# The largest component of G(n, p)

Below is an question related to largest /giant component :

Let $$p >> \frac{1}{n}$$. Prove that, for every $$ε > 0$$, a.a.s. the largest component of $$G(n, p)$$ has a size of at least $$(1 − ε)n$$.

So what I understand from the largest component is it will be the largest connected component present in a random graph. I was planning to solve it in a way as it is solved for w.h.p $$G(n, p)$$ contains a tree component of the given size. For the latter, the idea was to take the expectation and prove it tends to infinity and then prove $$Var X/(EX)^2$$ tends to zero ( where X represents the no of tree component of the given size) but the problem is I do not know how to calculate expectation for a giant component (like in case of trees the expectation is choosing k vertices out of n and multiplying it with no of ways of drawing a tree and the probability of having an edge and so on).

Could anyone please help me solve this question?

Thank you all.

## 1 Answer

Let $$V_1,...,V_m\subset V(G(n,p))=:V$$ be all the possible choices of $$\varepsilon n$$ vertices of $$G(n,p)$$, that is, $$|V_i|=\varepsilon n$$ and $$m={n\choose \varepsilon n}$$.

And we define the event $$A_i=\{e(G[V_i,V\setminus V_i])= 0\}$$, where $$e(G[V_i,V\setminus V_i])$$ count the number of edges between $$V_i$$ and $$V\setminus V_i$$ in $$G(n,p)$$.

Then, we want to prove that

$$P\left(\bigcup_{i=1}^m A_i\right) \to 0.$$

As $$A_i$$ happening is equivalent to all the edges between $$V_i$$ and $$V\setminus V_i$$ not appearing in $$G(n,p)$$ we have that

$$P(A_i)= (1-p)^{(\varepsilon n)(1-\varepsilon)n}\leq e^{-\varepsilon(1-\varepsilon) p n^2}.$$

By the union bound and using $${n\choose k}\leq (\frac{e n}{k})^k$$, we get

\begin{align*} P\left(\bigcup_{i=1}^m A_i\right) &\leq \sum_{i=1}^m P(A_i) \\ &\leq {n\choose \varepsilon n} e^{-\varepsilon(1-\varepsilon) p n^2} \\ &\leq \left(\frac{e n}{\varepsilon n}\right)^{\varepsilon n} e^{-\varepsilon(1-\varepsilon) p n^2} \\ &= e^{-\varepsilon(1-\varepsilon) p n^2 + \varepsilon n (1-\log(\varepsilon))} \\ &= e^{-\varepsilon n((1-\varepsilon) p n + 1-\log(\varepsilon))} \to 0\\ \end{align*}

because $$p n \to \infty$$.