OPEN
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$.
Conjectured by Erdős and Faudree, who showed that $2^{n/2}<f(n) \leq 2^{n-2}$. The first problem was solved by Verstraëte
[Ve04], who proved
\[f(n)\ll 2^{n-n^{1/10}}.\]
This was improved by Nenadov
[Ne25] to
\[f(n) \ll 2^{n-n^{1/2-o(1)}}.\]
One can also ask about the existence and value of $\lim f(n)^{1/n}$.