Probabilistic Method: the size of largest induced triangle-free subgraph of $G(n, 1/2)$ is $\Theta(\log(n))$?

Question

It's a related homework from the MIT course 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(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)$?

Answer 1

The logic is correct. The statement $\binom nk e^{-\Theta(k^2)}=\Theta(\frac{n^k}{e^{k^2}})$ should be amended to $\binom nk e^{-\Theta(k^2)}=O(\frac{n^k}{e^{k^2}})$, since $\binom nk$ is not $\Theta(n^k)$, but this does not impact the rest of the argument.

It's also a really hard approach to take for the lower bound. For the upper bound, you get to save a lot of work by appealing to the $e^{-\Theta(n^2)}$ argument. For the lower bound, you'd need to find the variance of $X$, which requires looking carefully at triangle-free graphs.

Instead, consider that you actually have a lot of wiggle room when $\Theta(\log n)$ is all you need to prove. Instead of looking at arbitrary triangle-free subgraphs of order $O(\log n)$, you can add extra conditions on those subgraphs.

Is there a type of subgraph of order, say, $k \sim 2 \log_2 n$, which is definitely triangle-free, and exists in $G(n, \frac12)$ with probability $1-o(1))$? You have already seen such a result in this class, you just have to realize it.

Answer 2

This is a complete solution based on Misha's hint:

From the content of note(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)}=O(\frac{n^k}{e^{k^2}})$$ If $k\gg\log n$, we have $\mu=o(1)$. Then by Markov's inequality, $P(X\ge 1)\le \mu = o(1)$, which implies that with probability $1-o(1)$ the graph has no induced trianle-free subgraph of size $k$.

On the other hand, the two-point concentration theorem for clique number(Section 4.3 in the note) gives that when $k \sim 2\log_2 n$, with probability $1-o(1)$ there exists an independent set of size $k$ in $G(n, 1/2)$. Since an independent set definitely induces a triangle-free subgraph, then we can conclude that with probability $1-o(1)$ there exists an induced triangle-free subgraph of size $\Theta(\log n)$.