On graphs with subgraphs having large independence numbers

Let G be a graph on n vertices in which every induced subgraph on ${s}={\log}^{3}\, {n}$ vertices has an independent set of size at least ${t}={\log}\, {n}$ . What is the largest ${q}={q}{(n)}$ so that every such G must contain an independent set of size at least q ? This is one of the several related questions raised by Erdős and Hajnal. We show that ${q}{(n)}= \Theta({\log}^{2} {n}/{\log}\, {\log} \,{n})$ , investigate the more general problem obtained by changing the parameters s and t , and discuss the connection to a related Ramsey‐type problem. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 149–157, 2007