# 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.