All Random Solved Random Open
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$.
Conjectured by Erdős, Fajtlowicz, and Stanton. It is known that $F(5)=3$ and $F(7)=4$. Ramsey's theorem implies that $F(n)\gg \log n$. Bollobás observed that $F(n)\ll n^{1/2+o(1)}$. Alon, Krivelevich, and Sudakov [AKS07] have improved this to $n^{1/2}(\log n)^{O(1)}$.
Additional thanks to: Zachary Hunter