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.


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.