← All problems

Erdős Problem #84 — Cycle sets of graphs

29 years old · traced to

For an integer n≥3n\ge 3 and a graph GG on nn vertices, define its cycle set by

S(G)={ℓ∈{3,…,n}:G contains a cycle of length ℓ}.\mathcal{S}(G)=\{\ell\in\{3,\ldots,n\}:G\text{ contains a cycle of length }\ell\}.

Let f(n)f(n) be the number of distinct sets S(G)\mathcal{S}(G) attained by graphs on nn vertices. The two requested asymptotic assertions, as nn tends to infinity through the integers, are

f(n)=o(2n),f(n)2n/2⟶∞.f(n)=o(2^n),\qquad \frac{f(n)}{2^{n/2}}\longrightarrow\infty.

Erdős Problems #84

Background

A cycle set records which cycle lengths occur, rather than the number of cycles or the structure of any particular cycle. Since there are 2n−22^{n-2} subsets of the possible lengths {3,…,n}\{3,\ldots,n\}, the question asks how many of these candidate patterns can actually arise from an nn-vertex graph. Erdős and Faudree posed the counting problem and gave initial exponential upper and lower bounds; the two limits above are the sharper questions associated with it. Erdős Problems #84

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.