Linearly many edges force certain cycle lengths
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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), 97105.

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.), 4767, SpringerVerlag, Berlin, 1996.
