Status
On this page
Status
Topics
Status
On this page
Status
Topics
The cycle set of a graph on vertices is a set such that there is a cycle in of length if and only if . Let count the number of possible such .
Prove that .
Prove that .
Source: erdosproblems.com/84
No claim settles this problem.
Open: the site labels the problem OPEN (proof-claims tab and
thread as of 2026-10-07), and the frontmatter standing is derived from the
two claim pages under claims/, the problem's two assertions being its parts.
The first, , is Verstraëte's refereed theorem [Ve04] in the
stronger form
(claim page (Verstraëte, 2004),
accepted, partial), sharpened by Nenadov [Ne25] to
(claim page (Nenadov, 2025),
accepted, partial); the second, , is open, so the
standing is open. One partial proof claim is registered on the tab:
Botsford's Zenodo preprint (claim 351 on the tab, registered 25 September
2026, made using GPT-6 Astra and Opus 5.5, as the tab names them) asserts
the explicit lower bound for all by
three computer-assisted constructions. It gets no claim page because it
settles no instance of either assertion: a constant factor over is
not the divergence asked, and is not addressed. The site's
remark credits the first problem to Verstraëte with Nenadov's improvement,
and the site labels the problem OPEN. The site states that a listing on the
tab is no guarantee of correctness.