Large Independent Sets from Local Considerations

The following natural problem was raised independently by Erdos-Hajnal and Linial-Rabinovich in the early '90 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 the previously best lower bounds due to Linial-Rabinovich, Erdos-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) >= Omega (n(5)/(12)). This confirms a conjecture of Erdos and Hajnal that alpha (G) should be at least n(1/3)+(epsilon) and brings the exponent halfway 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 (The 2-density of a graph H is defined as m(2)( H) := max(H)'subset of H,|H' |>= 3 (e(H')-1) / (vertical bar H'vertical bar - 2) 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 Erdos-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.

Automated summary

This paper discusses a natural problem raised independently by Erdos-Hajnal and Linial-Rabinovich, and introduces new methods to attack the problem with improved bounds. The first approach is based on bounding Ramsey numbers of certain graphs, improving previous lower bounds. The second approach deals with upper bounds by reducing the original question to a extremal problem.