Problem #82: Let $F(n)$ be maximal such that every graph on $n$ vertices...

---

Progress

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)}$.

In [Er93] Erdős asks whether, if $t(n)$ is the largest trivial (either empty or complete) subgraph which a graph on $n$ vertices must contain (so that $t(n) \gg \log n$ by Ramsey's theorem), then is it true that\[F(n)-t(n)\to \infty?\]Equivalently, and in analogue with the definition of Ramsey numbers, one can define $G(n)$ to be the minimal $m$ such that every graph on $m$ vertices contains a regular induced subgraph on at least $n$ vertices. This problem can be rephrased as asking whether $G(n) \leq 2^{o(n)}$.

Fajtlowicz, McColgan, Reid, and Staton [FMRS95] showed that $G(1)=1$, $G(2)=2$, $G(3)=5$, $G(4)=7$, and $G(5)\geq 12$. Boris Alexeev and Brendan McKay (see the comments and this site) have computed $G(5)=17$, $G(6)\geq 21$, and $G(7)\geq 29$.

See also [1031] for another question regarding induced regular subgraphs.