Regular induced subgraphs

Let \( f(n)\) be the largest integer for which every graph of \( n\) vertices contains a regular induced subgraph of greater than \( f(n)\) vertices. Ramsey's theorem implies that a graph of \( n\) vertices contains a trivial subgraph or a complete subgraph of \( c\log n\) vertices.

Conjecture: (Proposed by Erdös, Fajtlowicz and Staton \( ^{[2]}\))

\[ f(n) / \log n \rightarrow \infty . \]

Note that \( f(5)=3\) (since if a graph on \( 5\) vertices contains no trivial subgraph of \( 3\) vertices then it must be a pentagon). \( f(7)=4\) was proved by Fajtlowicz, McColgan, Reid, and Staton \( ^{[2]}\), and also McKay (personal communication) found that \( f(16)=5\) and \( f(17)=6\). Bollobás observed that  \( f(n)< n^{1/2+\epsilon}\) for \( n\) sufficiently large (unpublished).

Bibliography
1 P. Erdös, Some of my favourite problems in number theory, combinatorics, and geometry, Combinatorics Week (Portuguese) (São Paulo, 1994), Resenhas 2 (1995), 165-186.

2 S. Fajtlowicz, T. McColgan, T. Reid and W. Staton, Ramsey numbers for induced regular subgraphs, Ars Combinatoria 39 (1995), 149-154.