OPENHARDgraph theory
Let $F(n)$ be maximal such that every graph on $n$ vertices contains a regular induced subgraph on at least $F(n)$ vertices. Prove that $F(n)/\log n\to \infty$.
Notes: Ramsey's theorem gives F(n) >> log n. Alon, Krivelevich, and Sudakov proved F(n) <= n^{1/2} (log n)^{O(1)}.
AI Status: NONE · 0 total attempts