On the number of sets of cycle lengths (Q812791)

A subset \(S\) of \(\{1,2,\dots ,n\}\) is a cycle set if there exists a graph \(G\) on \(n\) vertices such that the set of lengths of cycles in \(G\) is \(S\). Erdős conjectured that the number of cycle sets on \(\{1,2,\dots ,n\}\) is \(o(2^n)\). The author verifies this conjecture by proving that there exists an absolute constant \(c\geq 0.1\) such that the number of cycle sets on \(\{1,2,\dots ,n\}\) is \(o(2^{n-n^c})\).