Suppose $G$ is a graph that $|E(G)| \leq \epsilon |G|^2$, prove that there is $H \subset G$ such that $|H| \geq |G|/2$ and for all $v \in H$ we have $d_H(v) \leq 4 \epsilon |H| $.
$|G|$ is the number of vertices in $G$. $E(G)$ is the set of edges in $G$. $d_H(v)$ is the number of vertices in $H$ connected to $v$.
I tried to solve it by applying probabilistic method, but I failed. Easily you can find such $H$ that for all $v \in H$ we have $d_H(v) \leq 8 \epsilon |H| $.but about $4$...
Is there any hint?
Thanks.
No probabilistic method is necessary; a greedy algorithm is enough.
Start by taking $H = G$. For as long as there is a vertex $v$ with $\deg_H v > 4 \epsilon |H|$, delete $v$ from $H$.
This cannot be done more than $\frac12|G|$ times. For as long as $|H| \ge \frac12 |G|$, each time we delete a vertex, we lose more than $4 \epsilon |H| \ge 2 \epsilon |G|$ edges, so if we delete $\frac12 |G|$ vertices, we have lost more than $2\epsilon |G| \cdot \frac12 |G| = \epsilon |G|^2$ edges: more than the total number of edges in $G$.
So we have to stop sometime before then. When we stop, we still have more than $\frac12 |G|$ vertices left in $H$, but no vertex can be deleted: all vertices have $\deg_H v \le 4\epsilon|H|$.
We could actually be more careful than this, and get a maximum degree of $\frac83 \epsilon |H|$, by observing that if we keep deleting vertices that violate this property, then after $\frac12|G|$ steps we delete at least $$\frac83 \epsilon |G| + \frac83 \epsilon (|G|-1) + \dots + \frac83 \epsilon \left(\frac12|G|+1\right) > \epsilon |G|^2$$ edges. (In other words, keep track of $|H|$ when seeing how many edges we lose, rather than using the bound $|H| \ge \frac12 |G|$ at each step.)