Below is an question related to largest /giant component :

Let $p \gg \frac{1}{n}$. Prove that, for every $ε > 0$, a.a.s. the largest component of $G(n, p)$ has size 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 $\operatorname{Var} X/(EX)^2$ tends to zero (where $X$ represents the number of tree components 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 number 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.


Let $V_1,...,V_m\subset V(G(n,p))=:V$ be all the possible choices of $k$ vertices of $G(n,p)$ for $\varepsilon n \leq k \leq (1-\varepsilon)n$, that is, $m=2\sum_{k=\varepsilon n }^{n/2} {n\choose k}\leq 2^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)$.

Let's first prove the following Lemma:

Lemma: Whp, for every $i\in [m]$, $V_i$ sends edges to $V\setminus V_i$.

\begin{proof} 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) \leq (1-p)^{(\varepsilon n)(1-\varepsilon)n}\leq e^{-\varepsilon(1-\varepsilon) p n^2}.$$

By the union bound and using $m<2^n$, we get

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

because $p n \to \infty$.

Then, whp for every $i\in [m]$, $V_i$ sends edges to $V\setminus V_i$. \end{proof}

Let $U$ be the largest component of $G(n,p)$. Suppose we have whp $|U|\geq \varepsilon n$ for $\varepsilon>0$ sufficiently small.

Now, suppose by contradiction that $|U|\leq (1-\varepsilon)n$. Then, by the Lemma, there is at least one edge between $U$ and $V\setminus U$, contradicting the maximality of $U$.

Finally, it is enough to prove that there is sufficiently small $\varepsilon>0$ such that $|U|\geq \varepsilon n$ whp. And the proof of that follows easily from the Lemma (see comment of Misha Lavrov).