Improved bound on the number of cycle sets

Abstract

The cycle set of a graph $G$ is the set consisting of all sizes of cycles in $G$. Answering a conjecture of Erdős and Faudree, Verstraëte showed that there are at most $2^{n-n^{1/10}}$ different cycle sets of graphs with $n$ vertices. We improve this bound to $2^{n-n^{1/2-o(1)}}$. Our proof follows the general strategy of Verstraëte of reducing the problem to counting cycle sets of Hamiltonian graphs with many chords or a large maximum degree. The key new ingredients are near-optimal container lemmata for cycle sets of such graphs.

11 pages