Erdős Problems

Tags Prizes

SOLVED

Let $f(m,n)$ be maximal such that any graph on $n$ vertices in which every induced subgraph on $m$ vertices has an independent set of size at least $\log n$ must contain an independent set of size at least $f(n)$.

Estimate $f(n)$. In particular, is it true that $f((\log n)^2,n) \geq n^{1/2-o(1)}$? Is it true that $f((\log n)^3,n)\gg (\log n)^3$?

#804: [Er91]

graph theory

A question of Erdős and Hajnal. Alon and Sudakov [AlSu07] proved that in fact \[\frac{(\log n)^2}{\log\log n}\ll f((\log n)^2,n) \ll (\log n)^2\] and \[f((\log n)^3,n)\asymp \frac{(\log n)^2}{\log\log n}.\]