Problem 84

Erdős Problem #84: declared status 'open'. Formalized: no. The cycle set of a graph $G$ on $n$ vertices is a set $A\subseteq \{3,\ldots,n\}$ such that there is a cycle in $G$ of length $\ell$ if and only if $\ell \in A$. Let $f(n)$ count the number of possible such $A$. Prove that $f(n)=o(2^n)$. Prove that $f(n)/2^{n/2}\to \infty$. Prize: no. Tags: cycles, graph theory.