Erdős Problem #84 — Cycle sets of graphs
For an integer and a graph on vertices, define its cycle set by
Let be the number of distinct sets attained by graphs on vertices. The two requested asymptotic assertions, as tends to infinity through the integers, are
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 subsets of the possible lengths , the question asks how many of these candidate patterns can actually arise from an -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
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
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.