How many cycle sets are achievable on $n$ vertices? Prove $f(n)/2^{n/2}\to\infty$ (Erdős #84)
Statement
The cycle set of a graph $G$ on $n$ vertices is the set $A\subseteq\{3,\ldots,n\}$ such that $G$ contains a cycle of length $\ell$ if and only if $\ell\in A$. Let $f(n)$ count the number of sets $A\subseteq\{3,\ldots,n\}$ that arise as the cycle set of some graph on $n$ vertices. Prove that $f(n)=o(2^n)$. Prove that $f(n)/2^{n/2}\to\infty$. (The first part is settled: Verstraëte proved $f(n)\ll 2^{n-n^{1/10}}$, and Nenadov improved this to $f(n)\ll 2^{n-n^{1/2-o(1)}}$ — see background. The open problem is the second part: show that $f(n)/2^{n/2}\to\infty$. One can further ask whether $\lim f(n)^{1/n}$ exists, and what its value is.)
Acceptance. FULLY RESOLVES: a proof that $f(n)/2^{n/2}\to\infty$ — e.g. an explicit family of constructions realising $g(n)\,2^{n/2}$ distinct cycle sets on $n$ vertices with $g(n)\to\infty$, together with a proof that the realised sets are distinct and correctly counted — machine-checkable (Lean/Coq) preferred, else a complete written proof; OR a proof that $f(n)\ll 2^{n/2}$, refuting the conjecture. Determining $\lim f(n)^{1/n}$ (existence plus value, with proof) also fully resolves the problem. A finite computation alone cannot close the asymptotic claim. ADVANCES: a proven lower bound $f(n)\geq 2^{(1/2+c)n}$ for an explicit constant $c>0$, or $f(n)\geq g(n)2^{n/2}$ with an explicit $g(n)\to\infty$; an upper bound strictly improving Nenadov's $2^{n-n^{1/2-o(1)}}$ bound stated in the background; a proof that $\lim f(n)^{1/n}$ exists; or exact computation of $f(n)$ for all $n$ up to a stated bound via exhaustive enumeration of realisable cycle sets, with reproducible code and an exhaustiveness certificate (new data — none recorded on the source page or in OEIS). Deliver the proof file, or the enumeration code plus the verified table of $f(n)$.
Background
Conjectured by Erdős and Faudree, and raised by Erdős in [Er94b], [Er95], [Er96], and [Er97d]; listed as open on erdosproblems.com/84 (fetched 2026-07-13, status 'open', tagged 'graph theory | cycles'). Erdős and Faudree established the bounds $2^{n/2}<f(n)\leq 2^{n-2}$. The first conjecture, $f(n)=o(2^n)$, was solved by Verstraëte [Ve04], who proved the quantitative bound $f(n)\ll 2^{n-n^{1/10}}$; Nenadov [Ne25] improved this to $f(n)\ll 2^{n-n^{1/2-o(1)}}$. What remains is any superconstant gain over the Erdős–Faudree lower bound: does $f(n)/2^{n/2}\to\infty$? The source page also records the further question of the existence and value of $\lim f(n)^{1/n}$ — the known bounds confine any such limit to $[\sqrt{2},2]$, and Nenadov's bound still allows any value in that range. Cycle sets (also called cycle spectra) are strongly constrained combinatorial objects: the upper-bound proofs work by showing that graphs with many vertices cannot realise most subsets, while the lower bound comes from explicit constructions realising many spectra. No table of exact values of $f(n)$ is recorded on the source page, and no OEIS entry is cited. The attacker's tools: on the construction side, systematic gadget graphs (subdivisions, theta-graphs, clique/bipartite blocks glued at cut vertices) whose cycle sets can be prescribed — any scheme realising $\omega(2^{n/2})$ distinct spectra on $n$ vertices resolves the problem; on the data side, exhaustive enumeration of achievable cycle sets for small $n$ (graph search with isomorph rejection, or SAT per candidate spectrum) yielding certified exact values of $f(n)$, which would calibrate $\lim f(n)^{1/n}$ empirically and is publishable as a new sequence.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #84 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.