Erdős problem 809 — wave 6l

Date: 2026-07-27 UTC

Outcome: the live problem is still open, with no claimed proof and no current worker. The unresolved asymptotic case is \(C_7\). I did not solve that case uniformly, but obtained and independently rechecked the exact first nontrivial finite value

I use the requested claim labels throughout:

• [a] elementary-rigorous;
• [b] rigorous modulo the named source/theorem;
• [c] plausible or structural but unverified;
• [d] computational-only.

0. Mandatory live-page gate

[b] I accessed the Cloudflare-protected live page and its discussion with the Bright Data browser on 2026-07-27:

• problem 809;
• LaTeX view;
• discussion thread.

The live page reported:

• status OPEN;
• 0 claimed proofs;
• Currently working: None;
• Interested in collaborating: None;
• one comment, by Alfaiz at 06:30 on 20 March 2026, pointing out the

Bucić–Chen–Ma result for \(k\geq4\); the comment says the site was updated;

• last page edit: 1 April 2026.

Thus the mandatory stop condition was absent.

Exact current statement

To keep the mathematical content exact, here is a formal transcription of the definition in the live LaTeX view:

The exact question line on the live page is:

Is it true that, for all \(k\geq 3\), \[ > \chi_S(n,\lfloor n^2/4\rfloor+1,C_{2k+1})\sim n^2/8? > \]

[b] The same live page lists the following known results:

from Burr–Erdős–Graham–Sós; the conjectured asymptotic is now proved for every \(k\geq4\) by Bucić–Chen–Ma; and the page contrasts this with

and, for all large \(n\),

Consequently, [b] only \(k=3\), namely the target \(C_7\), remains from the displayed conjecture.

1. Primary-source literature audit

[b] I verified the following sources rather than relying on search-result summaries.

1. S. A. Burr, P. Erdős, R. L. Graham, and V. T. Sós,

Maximal antiramsey graphs and the strong chromatic number, J. Graph Theory 13 (1989), 263–282, DOI, official Erdős archive scan. Section 5, especially journal page 270, proves a quadratic lower bound for every fixed odd cycle of length at least seven. It treats \(C_7\) separately inside that proof and then asks whether the leading constant can be \(1/8\).

1. M. Bucić, K. Chen, and J. Ma,

On a maximal anti-Ramsey conjecture of Burr, Erdős, Graham, and Sós, arXiv:2603.18952 (2026). Theorem 1.2 proves, for fixed \(k\geq4\) and throughout the nontrivial edge range, \[ f(n,e,C_{2k+1}) =\frac e2+\frac n2\sqrt{e-\frac{n^2}{4}}+o(n^2). \] On PDF page 11, immediately after the proof, the authors explain that \(k\geq4\) is needed for their short-path length budget. They say that a more involved stability argument handles their second (near-Turán) case for \(k=3\), while their first (higher-density) case remains the bottleneck.

1. [b] The live page cites P. Erdős,

Problems and results in combinatorial analysis and combinatorial number theory, Graph Theory, Combinatorics, and Applications, Vol. 1 (1991), 397–406, at page 398. I verified the bibliographic record and that it is the source attached to problem 809; I did not find an independently accessible primary scan during this run.

[b] Targeted web/arXiv searches for the exact maximal anti-Ramsey \(C_7\) case, for papers citing arXiv:2603.18952, and for 2026 follow-ups found the Bucić–Chen–Ma paper and unrelated new work on \(P_4\), but no later primary source resolving \(C_7\). This is an honest search miss, not a proof that no such source exists.

2. Exact reduction used by the computation

For a fixed host graph \(H\), define its \(C_7\)-edge-conflict graph \(Q_7(H)\) as follows:

[a] Lemma. An edge-colouring of \(H\) makes every \(C_7\) rainbow if and only if it is a proper vertex-colouring of \(Q_7(H)\). Hence

Proof. Every \(C_7\) is rainbow exactly when every pair among its seven edges has different colours. Those and only those pairs are edges of \(Q_7(H)\).

\(\square\)

This turns the finite problem into an ordinary exact chromatic problem and, for a lower bound, it suffices to find a clique in every \(Q_7(H)\).

3. Exact finite result

3.1 Table

The verified table at the problem's prescribed edge count is:

For \(n=1,2\), the prescribed edge count exceeds \(\binom n2\), so I do not assign a value.

3.2 Elementary \(n\leq9\) witnesses

[a] For \(3\leq n\leq6\), no graph has a \(C_7\), so any host at the required edge count can be coloured with one colour.

[a] For \(n=7\), take any 13 edges inside a fixed six-vertex set and leave the seventh vertex isolated.

[a] For \(n=8\), take \(K_6\), an edge on the other two vertices, and one bridge joining these pieces. This has \(15+1+1=17\) edges, and every cycle is contained in a block of order at most six.

[a] For \(n=9\), take

It has \(3+3\cdot6=21\) edges. Independent-set vertices cannot be consecutive on a cycle, so a \(C_7\) would require at least four vertices from the three-vertex clique, which is impossible.

In every case the one-colour lower bound is tautological, so the value is exactly one. The verifier reconstructs each host and enumerates its \(C_7\)'s from scratch.

3.3 Explicit 13-colour witness for \(n=10\)

Let

put on \(A\) the paw with edges

put on \(B\) the diamond \(K_4-12\), with edges

and join two further adjacent vertices \(8,9\) to every vertex of \(A\cup B\). Thus

has

edges.

Use colours as follows:

• give the nine paw/diamond edges distinct colours \(0,\ldots,8\), in the

order \[ 04,15,25,16,26,56,07,37,47; \]

• colour \(8A\) with colour 9 and \(8B\) with colour 10;
• colour \(9A\) with colour 11 and \(9B\) with colour 12;
• colour \(89\) with colour 0.

[a] This is a valid 13-colouring. Indeed, a \(C_7\) cannot use \(89\): an alternative \(8\)-to-\(9\) path of length six would need five distinct vertices inside one of the two four-vertex components. A \(C_7\) also cannot use only one of \(8,9\), since deleting that hub leaves a path inside one four-vertex component. Therefore every \(C_7\) uses both hubs but not \(89\). The two base paths between the hubs cannot both lie in the same four-vertex component, because together they use five base vertices. Hence at each hub the cycle uses at most one spoke from each same-colour component class. All base edges already have distinct colours, proving the claim.

For machine-independent identification, this host has graph6 string

I?`bKr~~w

and the standalone checker lists all 26 edges and all 26 colour values.

3.4 Exhaustive lower bound

[d] Computational theorem. Every simple 10-vertex graph \(H\) with 26 edges has a clique \(K_{13}\) in \(Q_7(H)\). Consequently every rainbow-\(C_7\) colouring of \(H\) needs at least 13 colours.

The exhaustive check did the following.

1. nauty-geng 2.8.8 generated one graph6 representative of every unlabelled

10-vertex graph with exactly 26 edges. There were exactly 828,728 records. The generated byte stream had SHA-256 ded24c07f48b643935965874833ecbe1fc443481b814917571e72f30740aac77.

1. A separate C++20 scanner decoded graph6 itself.
2. For every host it enumerated all simple 7-cycles by DFS. The least cycle

vertex was fixed as the start and one of the two orientations was retained, so every unoriented \(C_7\) appeared exactly once.

1. Each cycle made its seven host-edge indices a clique in \(Q_7(H)\).
2. A bitset branch-and-bound search found a \(K_{13}\). On every successful

host the returned 13-bit certificate was separately checked pairwise against the constructed conflict graph.

Because \(\chi(Q_7(H))\) is invariant under relabelling, one representative of each isomorphism class is sufficient. The dependence on nauty's exhaustive unlabelled generation is why this result is marked [d], not [a].

The final scan output was:

explicit C7-free hosts: PASS (chi_S=1 for 3 <= n <= 9)
n=10 witness: PASS (26 edges, 292 C7s, 276 conflicts, K13 and 13-coloring)
exhaustive lower bound: PASS (828728 unlabelled hosts; every Q7(G) contains K13; graph6 SHA256=ded24c07f48b643935965874833ecbe1fc443481b814917571e72f30740aac77, matches recorded digest)
FINAL CHECK: chi_S(10,26,C7)=13 (computational-only)

For the explicit host \(H_0\), two structurally independent Python cycle enumerators—DFS and iteration over all 7-subsets and cyclic permutations—both found exactly 292 cycles and the same cycle set. They produced a conflict graph with 276 edges. The following 13 host edges were independently checked to form a conflict clique:

Together with the explicit 13-colouring, this also certifies \(\chi(Q_7(H_0))=13\).

[d] Corollary. \(\operatorname{ex}(10,C_7)=25\): the exhaustive \(K_{13}\) result forces a \(C_7\) at 26 edges, while \(K_{5,5}\) is a 25-edge \(C_7\)-free graph.

4. Reproduction code

The entry point is:

python runs/erdos809_wave6l_verify.py

It compiles and invokes the transparent C++ scanner automatically. Required local programs are Python 3.12+, g++ with C++20, and nauty-geng. On this VM the full run took about 35 seconds. A fast construction-only check is:

python runs/erdos809_wave6l_verify.py --quick

Files:

• runs/erdos809_wave6l_verify.py — standalone re-verification entry point,

graph6 cross-check, two independent cycle enumerators, explicit witnesses, colouring/clique checks, generator checksum, and exhaustive-scan driver;

• runs/erdos809_wave6l_scan.cpp — auditable exhaustive conflict-graph and

clique scanner compiled by the Python entry point.

The core checked equivalence is implemented literally:

for cycle in cycles:
    edge_ids = [index[cycle_edge] for cycle_edge in cycle]
    for u, v in combinations(edge_ids, 2):
        conflict[u].add(v)
        conflict[v].add(u)

and the lower-bound scanner accepts a host only after it has found and then pairwise rechecked 13 mutually conflicting host edges.

5. What remains and the precise wall

[b] In the Bucić–Chen–Ma higher-density case, two selected “good” edges are joined using a path \(P_1\) of length at most three, a filler of length

and a closing path of length four. For \(k=3\), the filler length becomes

which is negative as soon as \(\ell(P_1)\geq2\). This is the exact numerical failure of that proof template, not merely a vague loss in constants.

[c] A sufficient missing lemma within their template would be a higher-density structural statement producing the required number

of edges that are pairwise co-contained in \(C_7\), or a replacement colour-counting argument of the same strength that does not demand pairwise co-containment. Their present distance-\(\leq3\) and exact-length-4 path lemmas do not supply the necessary \(C_7\) length budget. I do not claim that the stronger pairwise lemma is true; it precisely identifies what would make the existing induction close.

[d] Extending only the finite table to \(n=11\) is already outside the few-CPU-minute budget. nauty-geng -u 11 31:31 counted 70,065,437 unlabelled hosts in 25.9 CPU-seconds. At the measured \(n=10\) scanner rate, even before allowing for the larger cycle/conflict graphs, a corresponding scan costs about 0.8 core-hours; a realistic allowance is 0.8–1.5 core-hours (roughly USD 0.08–0.15 at USD 0.10 per vCPU-hour). Such a scan would still give only another finite value and cannot supply the uniformity needed for the asymptotic problem.

PARTIAL: The live problem remains open only for C7; exact computation and an explicit certified witness give chi_S(10,26,C7)=13, while the uniform high-density path-length lemma needed for the n→∞ asymptotic is still missing.