  The following natural problem was raised independently by Erd\H{o}s-Hajnal
and Linial-Rabinovich in the late 80's. How large must the independence number
$\alpha(G)$ of a graph $G$ be whose every $m$ vertices contain an independent
set of size $r$? In this paper we discuss new methods to attack this problem.
The first new approach, based on bounding Ramsey numbers of certain graphs,
allows us to improve previously best lower bounds due to Linial-Rabinovich,
Erd\H{o}s-Hajnal and Alon-Sudakov. As an example, we prove that any $n$-vertex
graph $G$ having an independent set of size $3$ among every $7$ vertices has
$\alpha(G) \ge \Omega(n^{5/12})$. This confirms a conjecture of Erd\H{o}s and
Hajnal that $\alpha(G)$ should be at least $n^{1/3+\varepsilon}$ and brings the
exponent half-way to the best possible value of $1/2$. Our second approach
deals with upper bounds. It relies on a reduction of the original question to
the following natural extremal problem. What is the minimum possible value of
the $2$-density of a graph on $m$ vertices having no independent set of size
$r$? This allows us to improve previous upper bounds due to Linial-Rabinovich,
Krivelevich and Kostochka-Jancey. As part of our arguments we link the problem
of Erd\H{o}s-Hajnal and Linial-Rabinovich and our new extremal $2$-density
problem to a number of other well-studied questions. This leads to many
interesting directions for future research.
