Prove that G has a triangle-free induced subgraph with at least $\frac{n}{15 \sqrt{3}}$ vertices.

Question

Problem: Let G be an n-vertex graph with at most 100n triangles. Prove that G has a triangle-free induced subgraph with at least $\frac{n}{15 \sqrt{3}}$ vertices.

Proof Given: Choose a subgraph $H \subset G$ by picking each vertex independently with probability $p \in[0,1]$, to be determined. Let $X = |V(H)|$, the number of chosen vertices. Let $A_v$ be the event that v is in a triangle and $Y_v$ be its indicator. Then $Y = \sum_{v \in H} Y_v$ is the number of "bad" vertices. Then the number of "good" vertices (not in a triangle) is $X-Y$. $$E[X-Y] = E[X] -E[Y] = np-100n\cdot p^3 = n(p-100p^3)$$ Consider the function $f(p) = p-100p^3$. Then, $f'(p)=1-300p^2$ and $f'(p)=0$ for $p=\frac{1}{\sqrt{300}}=\frac{1}{10\sqrt{3}}$, i.e. $f(p)$ is maximized at $p=\frac{1}{10\sqrt{3}}$. Let $p=\frac{1}{10\sqrt{3}}$. Then, $$E[X-Y] = n(\frac{1}{10\sqrt{3}}-\frac{100}{1000\sqrt{3}})^3) = n(\frac{1}{10\sqrt{3}}- \frac{1}{10\sqrt{3}^3}) = \frac{n}{15\sqrt{3}}$$

So there must exist a subgraph with at least ${n\over 15\sqrt{3}}$ vertices that has no triangle.

My question is, why is $E[Y] = 100np^3$? Is this actually an upper bound on $E[Y]$?

Answer 1

I would say that the random process is poorly described. The idea is:

1. We choose a subgraph $H$ of $G$, by including each vertex with probability $p$.
2. For every triangle in $H$, we mark one arbitrary vertex of that triangle.
3. We choose a smaller subgraph $H'$ of $H$ by keeping only those vertices of $H$ which were not marked. (In particular, $H'$ does not have any triangles, because each triangle contains a marked vertex.)

Now, $X$ can be the number of vertices in $H$ (as in the proof you gave) and $Y$ can be the number of triangles. The expected number of triangles $\mathbb E[Y]$ is at most $100 np^3$ by linearity of expectation: there are at most $100n$ triangles in $G$, and each one is a triangle in $H$ with probability $p^3$.

Then the number of marked vertices is at most $Y$: here, there is another "at most" because a vertex could get marked multiple times by multiple triangles that contain it.

Finally, this means that the number of vertices in $H'$ is at least $X-Y$, and from there the proof continues as written.