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}

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

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

3. 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](https://uu.diva-portal.org/smash/record.jsf?pid=diva2:2077189).

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

4. 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:

| \(m\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|

| \(d(m)\) | 1 | 1 | 2 | 4 | 6 | 10 | 16 | 25 | 39 | 63 | 99 |

| \(m\) | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |

|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|

| \(d(m)\) | 158 | 253 | 402 | 639 | 1021 | 1633 | 2617 | 4153 | 6633 | 10460 |

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:

| \(n\) | unlabeled graphs checked | exact \(f(n)\) | \(d(n-1)\) |

|---:|---:|---:|---:|

| 3 | 4 | 2 | 2 |

| 4 | 11 | 4 | 4 |

| 5 | 34 | 6 | 6 |

| 6 | 156 | 11 | 10 |

| 7 | 1,044 | 21 | 16 |

| 8 | 12,346 | 40 | 25 |

| 9 | 274,668 | 75 | 39 |

| 10 | 12,005,168 | 133 | 63 |

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:

| maximum edges | graphs checked | distinct masks seen |

|---:|---:|---:|

| 12 | 44,230 | 128 |

| 13 | 119,645 | 198 |

| 14 | 312,433 | 245 |

| 15 | 780,240 | 247 |

| 16 | 1,850,130 | 247 |

| 17 | 4,146,028 | 247 |

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

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

3. **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.