Logo
All Random Solved Random Open
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}$.

Additional thanks to: Tuan Tran