Linearly many edges force certain cycle lengths

Problem (proposed by Erdös)($100)

Is there a sequence \(A\) of density \(0\) for which there is a constant \(c(A)\) so that for \(n > n_0(A)\), every graph on \(n\) vertices and \(c(A)n\) edges contains a cycle whose length is in \(A\)?

Erdös [2] said,

I am almost certain that if \( A\) is the sequence of powers of \( 2\) then no such constant exists. What if \( A\) is the sequence of squares? I have no guess. Let \( f(n)\) be the smallest integer for which every graph on \( n\) vertices and \( f(n)\) edges contains a cycle of length \( 2^k\) for some \( k\). I think that \( f(n)/n \rightarrow \infty\) but that \( f(n) < n ( \log n)^c\) for some \( c > 0\).

Alon pointed out that \( f(n) \leq c n \log n\) using the fact [1] that graphs with \( n\) vertices and \( c k ^{1+1/k}\) edges contain cycles of all even lengths between \( 2k\) and \( 2k n ^{1/k}\) (and then take \( k\) to be about \( \log n/2\)).

Bibliography
1 J. A. Bondy and M. Simonovits, Cycles of even length in graphs, J. Comb. Theory Ser. B 16 (1974), 97-105.

2 P. Erdös, Some of my favorite problems and results, The Mathematics of Paul Erdös (R. L. Graham and J. Nešetril, eds.), 47-67, Springer-Verlag, Berlin, 1996.