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), 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.
|