It's a related homework from the MIT [course](https://yufeizhao.com/pm/) Probabilistic Methods in Combinatorics (the text book is *The Probabilistic Methods* by Alon and Spencer, but this exercise is not from the original book):

> 
> Prove that with probability $1-o(1)$, the size of the largest subset of vertices of $G(n, 1 / 2)$ inducing a triangle-free subgraph is $\Theta(\log n)$.
> 
> 
> 

What I have done on this problem:

From the content of [note](https://yufeizhao.com/pm/probmethod_notes.pdf)(Page 90) for this course, we know that the probability that $G(n,1/2)$ is triangle-free is $e^{-\Theta(n^2)}$.
Let $X$ be the number of triangle-free induced subgraph of size $k$ in $G(n,1/2)$. Then we have
$$\mu=E[X]={n\choose k}e^{-\Theta(k^2)}=\Theta(\frac{n^k}{e^{k^2}})$$.

If $k=\omega(\log n)$, we have $\mu=o(1)$. Then by Markov's inequality we have $P(X\ge 1)\le \mu = o(1)$, which implies that the graph has no induced trianle-free subgraph of size $k$ with probability $o(1)$.

On the other hand, let $\sigma^2$ be the variance of $X$. If $k=o(\log n)$, we have $\mu\rightarrow \infty$. Suppose we already have $\sigma^2=o(\mu^2)$, Chebyshev's inequality gives
$$P(X=0)\le P(|X-\mu|\ge \mu)\le \frac{\sigma^2}{\mu^2}=o(1)$$
Thus $P(X\ge 1)\ge 1-o(1)$, meaning that the graph admits a triangle-free induced subgraph of size $k$ with probability $1-o(1)$.

My questions are:

1. Is my train of thought to solve this exercise correct?
2. If it's correct, how to prove that $\sigma^2=o(\mu^2)$?