Erdős problem 84 — wave 7e

Accessed 2026-07-27 UTC. Outcome: a certified finite lower bound \(f(11)\ge 247\), an independent reproduction of the now-known exact table through \(n=10\), and a precise reduction of the surviving asymptotic question to counting distance sets. The asymptotic question is not solved.

Claim labels

• (a) elementary-rigorous: proved below from definitions.
• (b) rigorous-modulo-named-result/source: depends on the cited theorem,

primary document, or the documented completeness of nauty-geng.

• (c) plausible/structural-unverified: evidence or a proposed direction,

not a theorem.

• (d) computational-only: exhaustively checked or certificate-checked by

the supplied code, but not promoted to a general theorem.

Step 0: live-page check (done before mathematics)

I fetched the live page through the Bright Data browser path, not datacenter curl. The browser reported page title 84 | Erdős Problems and final URL https://www.erdosproblems.com/84.

The following is the problem statement verbatim (with only Markdown math delimiters added):

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\).

The live status/marker audit was:

• status: OPEN;
• comments: 0;
• claimed proofs: 0;
• “Likes this problem”: None;
• “Interested in collaborating”: None;
• “Currently working on this problem”: None;
• “This problem looks difficult”: None;
• “This problem looks tractable”: None;
• both displayed formalisation-interest markers: None;
• “Formalised statement?”: No; “Related OEIS sequences”: Possible;
• the page cites [Er94b][Er95][Er96][Er97d], and tags the problem “graph

theory | cycles”.

Thus the mandatory stop condition did not fire.

The page's listed known results are that Erdős and Faudree obtained \(2^{n/2}<f(n)\le 2^{n-2}\), Verstraëte solved the first displayed problem with

and Nenadov improved this to

It also asks about existence and value of \(\lim f(n)^{1/n}\). (b: live-page source-verified.) Consequently, the unresolved displayed demand is the lower-growth limit \(f(n)/2^{n/2}\to\infty\).

Literature audit

I searched by the exact problem language, title, author, and citations, and then read the relevant full primary documents rather than relying on search snippets.

1. Jacques Verstraëte, On the Number of Sets of Cycle Lengths,

Combinatorica 24(4) (2004), 719–730, DOI 10.1007/s00493-004-0043-6. The DOI, journal metadata, and abstract exist and state that the \(o(2^n)\) conjecture is proved with an exponent saving \(n^c\), \(c\ge 0.1\). (b.)

1. Rajko Nenadov, Improved bound on the number of cycle sets,

arXiv:2501.09904, subsequently Combinatorial Theory 6(1) (2026), #17, DOI 10.5070/C66165704. I read the peer-reviewed 2026 version. Its Theorem 1.1 is the explicit bound \[ f(n)\le 2^{\,n-\Omega(\sqrt n/\log^{3/2}n)}. \] On pages 2–3 it calls Faudree's \(2^{n/2}\) construction the best known lower bound and says that even \(2^{(1+c)n/2}\), for fixed \(c>0\), would be interesting. (b.)

1. A directly relevant source newer than the references currently displayed

on the live page is Alvin Dunås, The number of sets of cycle lengths for graphs on n vertices, Uppsala University project report 2026:24, June 2026, repository record and full text. The thesis explicitly says the lower-limit question remains open. It:

• proves the distance-set reduction in the next section;
• improves the constant in the elementary lower bound, but not to an

unbounded factor;

• gives \(d(n)\le O(\rho^n)\) for an explicit

\(\rho\approx1.7004\);

• computes \(f(1),\ldots,f(10)\).

These are claims made in a completed master’s thesis, not a claimed solution or a current-worker marker. (b.)

1. The distance-set numbers are [OEIS

A067247](https://oeis.org/A067247). OEIS is not a primary proof source; I use it only as an external data comparison and recompute the values used here. (d.)

The four original Erdős-source titles and metadata are also present in the Dunås bibliography: the 1994 Math. Pannonica paper, the 1995 favourite problems article, the 1996 cycles-and-colourings article, and the 1997 Discrete Mathematics article. I did not obtain clean searchable full text for all four, so I make no page-level claim about them beyond the live page's and the later primary papers' attribution. The targeted search found no other primary paper claiming a lower-limit proof. This is a reported search miss, not a proof that no such paper exists. (c.)

1. Exact hub–path reduction

Let \(P_m\) be the path on vertices \(0,1,\ldots,m-1\). Add one new hub \(h\) and join \(h\) precisely to the vertices in \(A\subseteq\{0,\ldots,m-1\}\); call the resulting graph \(G_A\). Define the positive distance set

Proposition.

Proof. The graph obtained after deleting \(h\) is a tree, so every cycle uses \(h\). A simple cycle uses exactly two hub edges, say \(ha\) and \(hb\), and between \(a\) and \(b\) it must use the unique path in \(P_m\). Its length is therefore \(1+|a-b|+1=|a-b|+2\). Conversely, every distinct pair \(a,b\in A\) supplies exactly this cycle. This proves (1). (a.)

Let

Translation does not change distances, so every nonempty \(A\) can be normalised to contain \(0\). The singleton \(\{0\}\) represents the empty distance set. Hence enumerating the \(2^{m-1}\) subsets containing \(0\) is a complete computation of \(d(m)\). By (1),

(a.) This is Proposition 2.2 of Dunås, so it is a clean reduction, not a novelty claim from this run.

The standalone checker recomputes:

These are exact finite counts from exhaustive subset enumeration. (d.) The checker also constructs every \(G_A\) for all \(2^{1}+\cdots+2^{10}=2046\) subsets on path orders \(1,\ldots,10\), enumerates its simple cycles, and checks (1) independently. (d.)

The exact missing sufficient lemma is now particularly transparent:

Indeed, (2) makes the right-hand ratio at least \(1/\sqrt2\) times the left-hand ratio. (a.) No source found proves the premise of (3).

2. Independent exact table through \(n=10\)

I streamed every unlabeled graph from nauty-geng and computed its cycle set. Isomorphism preserves cycle lengths, so one representative per isomorphism class is sufficient. geng's guarantee that it generates all such representatives is the external assumption here; the installed version was Debian nauty 2.8.8+ds-5. The program family is documented in Brendan McKay and Adolfo Piperno, Practical graph isomorphism, II, Journal of Symbolic Computation 60 (2014), 94–112, DOI 10.1016/j.jsc.2013.09.003. (b,d.)

The cycle detector is elementary: for each target length \(\ell\), choose the minimum-labelled vertex \(s\) of a putative cycle, and depth-first enumerate simple \(\ell\)-vertex paths starting at \(s\), restricting every other vertex to be greater than \(s\), then test the closing edge. Every simple cycle has such a unique minimum, so the detector has neither false positives nor false negatives. (a.)

The result is:

Together with the trivial \(f(1)=f(2)=1\), this reproduces

(d.) It exactly matches Appendix A of the June 2026 Dunås thesis. This is an independent reproduction, not a new table.

3. New finite certificate from this run: \(f(11)\ge247\)

I generated the 780,240 unlabeled 11-vertex graphs having at most 15 edges and retained one graph6 witness for each observed cycle-set mask. This produced 247 distinct masks. The supplied Python file embeds all 247 graph strings; the generation step is therefore not trusted for the lower-bound certificate. It decodes every witness and recomputes its cycle set in two independent ways:

1. separate target-length searches that stop at the first cycle;
2. full enumeration of all simple cycles, rooted at their minimum vertex.

Both routines agree with all 247 claimed, pairwise-distinct masks. Every witness has 11 vertices and at most 15 edges. Therefore

(d.) This is an explicit finite construction/certificate, not an asymptotic result. It extends beyond the thesis's exact computation through \(n=10\), but I make no claim of global novelty.

For scale,

This is finite evidence only. (d.)

The search by cumulative edge cap was:

The stabilisation from 15 through 17 edges does not prove \(f(11)=247\); a graph with more edges could have a new cycle set. (c,d.)

4. Reproduction code and recorded run

Files:

• runs/erdos84_wave7e_reverify.py — standalone certificate checker,

distance-set enumerator, hub–path checker, and embedded exhaustive native loop for \(f(3),\ldots,f(10)\);

• runs/erdos84_fast_enum.cpp — the separately compiled streaming enumerator

used during exploration.

Run:

python runs/erdos84_wave7e_reverify.py

Recorded output:

WITNESSES: 247 distinct 11-vertex cycle sets verified (at most 15 edges each; sha256=4e497a95fddceab0b1b3823e25ca5a7f0b8435ea84ea8dfe39fa9c3359cbf65b)
HUB+PATH: C(G_A)=d(A)+2 checked for all 2046 subsets on path orders 1..10
DISTANCE SETS: d(0)..d(20) = [1, 1, 2, 4, 6, 10, 16, 25, 39, 63, 99, 158, 253, 402, 639, 1021, 1633, 2617, 4153, 6633, 10460]
EXACT (nauty): f(3)..f(10) = [2, 4, 6, 11, 21, 40, 75, 133]
ALL CHECKS PASSED

The full run took 33.99 seconds wall time, 39.51 CPU seconds, and about 79 MB peak RSS on this VM. (d.) Source hashes at the time of the run were:

37254e15989b5e992005c6627ca22925e224d9d5c6cafbee872eda1805de1c8c  runs/erdos84_wave7e_reverify.py
a204b855fcd0c184cc2120c7589c9431704bb85e241b4a9fbc78a8c9d194de7b  runs/erdos84_fast_enum.cpp

5. Exact wall and why the standard routes stall

The finite certificate (4) cannot settle the live problem. Three precise obstructions remain.

1. Distance-set counting. The hub construction would settle the problem

if the premise of (3) were proved. The known injection stores an arbitrary subset in roughly the upper half of the interval, giving about one bit per two positions. Adding lower points creates cross-differences in that same upper-half “channel”, destroying the simple decoding. No injective family with an unbounded multiplicative gain is known here. (a for the interference observation; c for the assertion that this is the useful route.)

1. Finite data do not give uniform growth. The values of \(d(m)\), the

exact \(f(n)\) table, and (4) all lie above the baseline by growing-looking finite factors, but no proved recurrence, supermultiplicativity statement, or uniform injection propagates those factors to arbitrary \(n\). Disjoint union is not automatically multiplicative: cycle sets combine by set union, so cycle lengths from different components can mask one another. (a for the union fact; c for interpreting the numerical trend.)

1. **Even exact \(f(11)\) is a larger computation, and would still be only

finite. There are 1,018,997,864 unlabeled graphs on 11 vertices. The measured \(n=10\) pipeline processed 12,005,168 graphs in 29.48 wall seconds (35.25 CPU seconds). A straight full \(n=11\) pass is therefore estimated at roughly 40–70 minutes and about one core-hour, allowing for the greater per-graph cycle-search cost. I did not run it because it exceeds the requested few-CPU-minute budget. Sharding would reduce wall time but not core-hours. (c: cost extrapolation.)**

Thus the concrete missing mathematical lemma is an unbounded-factor lower bound for the number of distinct positive distance sets (sufficient), or a different graph construction whose cycle-set signatures can be composed without masking. The concrete missing finite computation is a complete one-representative enumeration at \(n=11\), costing about one core-hour in the current implementation; it could establish or refute the guess \(f(11)=247\), but it would not resolve the asymptotic problem.

PARTIAL: certified 247 distinct cycle sets on 11 vertices, so f(11)>=247; reproduced exact f(1..10), but the required unbounded-factor lower bound remains open.