Erdős problem #556 — wave 6a

Accessed 2026-07-27. The independent checker is erdos556_wave6a_reverify.py.

Outcome

There are three separate conclusions, and they must not be conflated.

1. The live statement, literally quantified over all \(n\), is false.

I give a self-contained proof that \[ R_3(C_3)=R_3(K_3)=17>9=4\cdot 3-3. \] The lower bound is certified by an explicit algebraic 3-colouring of \(K_{16}\), not by a database lookup. Classification: (a) elementary-rigorous.

1. **For the intended \(n\geq 4\) problem, the first open odd case is still

\(R_3(C_9)\leq 33\). I do not solve that unrestricted case. I do prove the exact matching result for the substantial Toeplitz subclass (the colour of \(ij\) depends only on \(|i-j|\)): a Toeplitz colouring of \(K_{32}\) can avoid \(C_9\), while every Toeplitz 3-colouring of \(K_{33}\) has a monochromatic \(C_9\). The upper certificate consists of only six explicit cycles. Classification: (a) elementary-rigorous.**

1. As a small-case cross-check, the script independently verifies

\(R_3(C_4)=11\): it checks an explicit colouring of \(K_{10}\), reduces the upper bound to 648,000 tiny labelled cases, and eliminates those cases by two explicit \(C_4\) obstructions. Classification: (d) computational-only as established in this report (although the value is already a published known result).

The literal \(n=3\) defect was already pointed out in a live-page comment, so I make no novelty claim for it. I also make no literature-novelty claim for the Toeplitz observation; I did not find this certificate in the sources searched, which is only a search miss, not evidence of priority.

Step 0: authoritative live-page audit

I fetched the Cloudflare-protected page through the Bright Data browser path, then separately opened its discussion thread. The stop condition did not trigger:

• live badge: DECIDABLE, not solved or falsified;
• claimed proofs: 0;
• “Currently working on this problem”: None;
• “Interested in collaborating”: None;
• the page also showed no user in any of its other interest/work markers.

Therefore I proceeded.

Verbatim live statement

The following is the statement displayed at erdosproblems.com/556 (math typography transcribed into LaTeX, words unchanged):

Let \(R_3(G)\) denote the minimal \(m\) such that if the edges of \(K_m\) are \(3\)-coloured then there must be a monochromatic copy of \(G\). Show that \[ > R_3(C_n)\leq 4n-3. > \]

The page calls this a problem of Bondy and Erdős and says the inequality is best possible for odd \(n\). Its listed results are:

• Łuczak: \(R_3(C_n)\leq(4+o(1))n\) for all \(n\), and

\(R_3(C_n)\leq3n+o(n)\) for even \(n\);

• Kohayakawa, Simonovits and Skokan: the conjecture for sufficiently large

odd \(n\);

• Benevides and Skokan: \(R_3(C_n)=2n\) for sufficiently large even \(n\).

The page was last edited 2026-02-08 and links OEIS A389335.

All live comments

The discussion thread contained exactly two comments.

1. KentaKitamura, 2026-07-13 14:46. The comment observes that the

statement as written fails for \(n=3\), since \(C_3=K_3\) and \(R(3,3,3)=17>9\). It says the intended statement is presumably for \(n\geq4\), notes that both OEIS A389335 and the current Small Ramsey Numbers survey use that restriction, and says Erdős's 1981 wording also omitted it.

1. TerenceTao, 2025-09-01 15:43. “Technically, this problem has been

reduced to a decidable one (verifying a finite number of \(n\)), but remains open.”

Comments on the site are explicitly marked unverified. Everything used below from the first comment is therefore re-proved from scratch.

Literature and status audit

I checked the actual records or texts, rather than relying on the stale tracker metadata.

• Erdős's 1981 source,

1981-32.pdf, p. 4, contains the Bondy–Erdős \(4n-3\) formulation and gives no explicit \(n\geq4\) restriction. Classification: source verification.

• I also searched the primary 1973 Bondy–Erdős paper,

Ramsey numbers for cycles in graphs, JCTB 14 (1973), 46–54, DOI 10.1016/S0095-8956(73)80005-X80005-X). Its text concerns the two-colour cycle problem; a text search found no \(4n-3\) three-colour conjecture. This agrees with the 2026 survey's bibliographic warning.

• Crossref and the article record verify Łuczak's exact title

\(R(C_n,C_n,C_n)\leq(4+o(1))n\), JCTB 75 (1999), 174–187. Later primary papers quote it as the odd-cycle asymptotic \(R_3(C_n)=4n+o(n)\). I did not locate an openly extractable copy of the 1999 article itself. Classification: (b) rigorous-modulo-named-theorem.

• The primary 2005 proceedings paper by Kohayakawa, Simonovits and Skokan,

The 3-colored Ramsey number of odd cycles, explicitly says in its abstract that it verifies the conjecture for sufficiently large \(n\). Classification: (b).

• The primary Benevides–Skokan paper,

The 3-colored Ramsey number of even cycles, JCTB 99 (2009), 690–708, states as Theorem 1 that for every sufficiently large even \(n\), \(R(C_n,C_n,C_n)=2n\). Classification: (b).

• The current

Small Ramsey Numbers survey, revision 18, 2026-04-24 (DOI 10.37236/21), §6.3.1, gives the present concrete frontier:

• \(R_3(C_3),\ldots,R_3(C_8)=17,11,17,12,25,16\);
• first open odd case: \(R_3(C_9)\), with lower bound \(33\);
• first open even case: \(R_3(C_{10})\), with lower bound \(20\);
• the large-odd exact result and large-even exact result above.

This is a current-state survey rather than a new theorem used in my proofs.

• A directly relevant primary special-case result is Bosse–Song,

arXiv:1709.06130: \[ gr_k(K_3,C_9)=4\cdot2^k+1. \] At \(k=3\), every 3-colouring of \(K_{33}\) with no rainbow triangle has a monochromatic \(C_9\). Thus any counterexample to the open \(R_3(C_9)\leq33\) must contain a rainbow triangle. Classification: (b).

Searches for \(R_3(C_9)\), \(R(C_9,C_9,C_9)\), and post-2025 cycle-Ramsey papers produced the Gallai result and surveys, but no proof of the unrestricted case. This agrees with the live page and the April 2026 survey. I found no usable explicit numerical cutoff in the regularity/stability “sufficiently large” results; they prove finiteness but do not turn the remaining list into a small feasible computation.

Result 1: the live statement is false at \(n=3\)

Explicit \(K_{16}\) construction

Identify the vertices with \(\mathbb F_2^4\), represented by the integers \(0,\ldots,15\). Partition the fifteen nonzero difference vectors into

Colour \(xy\) by \(i\) when \(x\mathbin{\mathtt{xor}}y\in S_i\). Each \(S_i\) is XOR-sum-free: for distinct \(a,b\in S_i\), \(a\mathbin{\mathtt{xor}}b\notin S_i\). If a triangle \(x,y,z\) were monochromatic, then its three difference vectors

would all lie in one \(S_i\), a contradiction. Hence this is a 3-colouring of \(K_{16}\) with no monochromatic \(C_3\), so

The checker verifies the partition, all XOR-sum-free conditions, and all \(\binom{16}{3}=560\) triangles independently.

Matching upper bound

The familiar proof is short enough to include. First, \(R(3,3)=6\): at a vertex of a red/blue \(K_6\), three incident edges have one colour; an edge of that colour among their other ends closes a triangle, while if no such edge exists those three ends form a triangle of the other colour. A red 5-cycle whose complement is a blue 5-cycle shows \(R(3,3)>5\). The checker also brute-forces all \(2^{10}\) colourings of \(K_5\) and all \(2^{15}\) colourings of \(K_6\), finding respectively 12 and 0 labelled triangle-free colourings.

Now take any 3-colouring of \(K_{17}\) and a vertex \(v\). Among its 16 incident edges, at least six have one colour, say red. If the six other ends contain a red edge, it closes a red triangle with \(v\). Otherwise their \(K_6\) is blue/green, and \(R(3,3)=6\) gives a blue or green triangle. Thus \(R_3(C_3)\leq17\).

Consequently

This completely falsifies the literal live statement, but does not settle the intended \(n\geq4\) conjecture. Classification: (a) elementary-rigorous.

Result 2: independent exact check at \(n=4\)

The checker contains three explicit edge lists partitioning all 45 edges of \(K_{10}\). Each colour graph is checked by the equivalent condition that no pair of vertices has two common neighbours. Thus the colouring has no monochromatic \(C_4\), proving \(R_3(C_4)>10\).

For completeness, here is the reduction used for the upper bound. Let \(G\) be a \(C_4\)-free graph on 11 vertices with exactly 19 edges. (If a graph has more, delete edges.) For a vertex \(v\) of degree \(d\), put \(A=N(v)\) and let \(B\) be the other \(10-d\) vertices.

• \(G[A]\) has maximum degree at most one; otherwise a two-edge path in

\(A\), together with \(v\), is a \(C_4\). Hence \(e(A)\leq\lfloor d/2\rfloor\).

• Every vertex of \(B\) has at most one neighbour in \(A\); two such

neighbours, together with \(v\), form a \(C_4\). Hence \(e(A,B)\leq10-d\).

Therefore

For \(d\geq6\), the trivial \(e(B)\leq\binom{10-d}{2}\) is already below 19, except equality at \(d=6\); equality there makes \(B=K_4\), which itself has a \(C_4\). Thus \(\Delta(G)\leq5\).

The script exhausts only \(2^{10}\) and \(2^{15}\) graphs to verify

If \(d=5\), the displayed inequality gives

If \(\Delta(G)\leq3\), the handshake lemma gives \(e(G)\leq16\). The only remaining possibility is \(\Delta(G)=4\).

Choose a degree-4 vertex. Equality throughout is now forced:

• \(A\) induces a perfect matching;
• every one of the six vertices of \(B\) has exactly one neighbour in \(A\);
• \(G[B]\) is a 7-edge \(C_4\)-free graph;
• since \(\Delta(G)=4\), every fibre \(f^{-1}(a)\), \(a\in A\), has size at

most two, and \(\Delta(G[B])\leq3\).

There are 450 labelled possibilities for \(G[B]\) and 1,440 maps \(f:B\to A\) with fibres of size at most two. The script checks all 648,000 pairs. They all fail for one of two transparent reasons:

1. if \(uv\in E(B)\) and \(f(u),f(v)\) are matched in \(A\), then

\(f(u),u,v,f(v)\) is a \(C_4\);

1. if \(f(u)=f(v)\) and \(u,v\) have a common neighbour \(w\) in \(B\),

then \(f(u),u,w,v\) is a \(C_4\).

Thus \(\operatorname{ex}(11,C_4)\leq18\). If a 3-colouring of \(K_{11}\) had no monochromatic \(C_4\), its three colour graphs would cover at most \(3\cdot18=54\) edges, fewer than \(\binom{11}{2}=55\). Together with the explicit \(K_{10}\) colouring,

The finite terminal enumeration is why I label this report's proof (d) computational-only, despite its small transparent search space.

Result 3: the \(n=9\) conjecture is exact for Toeplitz colourings

Call a colouring of \(K_N\) Toeplitz if the colour of \(\{i,j\}\), \(0\leq i<j<N\), is a function only of the absolute difference \(j-i\). This is a natural structured family used in Ramsey searches and is closed under restricting to the first \(M<N\) vertices.

Lower construction on 32 vertices

For \(0\leq i<j<32\), let \(d=j-i\) and colour:

Colour 0 has four components, the residue classes modulo 4, each of order

1. Colour 1 is bipartite between residues \(0,2\pmod4\) and separately

between residues \(1,3\pmod4\). Colour 2 is bipartite between even and odd vertices. Hence no colour has an odd cycle of length 9. This is also the usual four-block lower construction and proves the unrestricted lower bound

Six-cycle upper certificate on 33 vertices

In any Toeplitz 3-colouring of \(K_{33}\), consider the four difference classes

Two receive the same colour. Every pair in \(D\) supports the following explicit 9-cycle; the absolute differences of consecutive vertices, including the closing edge, use only the pair in the left column.

All vertices in every row are distinct and lie in \(\{0,\ldots,32\}\). Thus the pair supplied by pigeonhole gives a monochromatic \(C_9\). The checker validates all six cycles and all \(3^4=81\) colour assignments.

It follows that the least \(N\) forcing a monochromatic \(C_9\) in every Toeplitz 3-colouring is exactly

The same upper certificate applies in particular to circulant colourings of \(K_{33}\). Classification: (a) elementary-rigorous.

This does not prove \(R_3(C_9)=33\): an arbitrary colouring need not make all edges of one difference class monochromatic. What it does prove is that a counterexample cannot be found in the entire difference-colouring search space, including the natural 2-adic extremal template.

Exact remaining wall for the unrestricted \(n=9\) case

The missing assertion is precisely:

The standard four-block construction already gives the matching lower bound, so there is no numerical slack.

Two large structured regions are now rigorously excluded:

• no-rainbow-triangle colourings, by Bosse–Song's Gallai-Ramsey theorem;
• all Toeplitz/difference colourings, by the six-cycle certificate above.

The large-\(n\) regularity/stability proof does not specialize to \(n=9\): its cluster sizes and error hierarchy require \(n\) above a huge “sufficiently large” threshold. The exact missing finite lemma would be a small-order stability/classification theorem saying that every \(C_9\)-free 3-colouring of \(K_{33}\) is close enough to the four-block template to make the 33rd vertex impossible. In computational language, the alternative is a checkable UNSAT certificate for the following CSP.

Use one ternary variable per edge of \(K_{33}\), or 1,584 Boolean one-hot variables. For every undirected 9-cycle \(Q\) and colour \(c\), impose

The checker recomputes

The direct encoding therefore has

• \(2{,}332{,}538{,}208{,}000\) cycle clauses;
• \(20{,}992{,}843{,}872{,}000\) cycle-literal occurrences;
• at least about 84 TB merely for 32-bit literal identifiers, before clause

delimiters, indexing, solver state, or a proof trace.

At a sustained \(10^6\) emitted clauses per second per core, merely writing the cycle clauses costs about 648 core-hours; solving and certifying UNSAT would be additional and cannot be estimated honestly without a radically more compact formulation. Consequently I did not launch this direct job. A lazy cycle-separation SAT loop avoids the 84 TB materialization, but no known bound controls how many cuts or conflicts are needed for the UNSAT case. That compact, independently checkable certificate—or the finite stability lemma above—is the exact remaining requirement.

Classification of this diagnosis: (a) for the encoding/count arithmetic; (c) plausible/structural-unverified for the proposed stability route; the unrestricted \(R_3(C_9)\leq33\) remains unproved.

Reproduction

Run:

python runs/erdos556_wave6a_reverify.py

Observed output:

n=3: checked 560 triangles in the K16 construction; brute-forced R(3,3)=6; hence R_3(C3)=17>9
n=4: checked an explicit K10 colouring and the finite ex(11,C4)<=18 reduction; hence R_3(C4)=11
n=9 Toeplitz subclass: K32 lower colouring and all 81 assignments on distances {1,2,4,8} checked; sharp transition is 32/33
full n=9 direct encoding: 528 edge variables (ternary), 777,512,736,000 undirected C9s, 2,332,538,208,000 cycle clauses, 20,992,843,872,000 cycle literals
ALL CHECKS PASSED in 0.709 seconds

The checker uses only the Python standard library. It contains all witness edge sets and cycles explicitly and does not call a SAT solver, nauty, OEIS, or the network.

Claim ledger

FOUND: The live statement is false at n=3 (R_3(C_3)=17>9); for the intended n>=4 problem, R_3(C_4)=11 and the sharp Toeplitz K32/K33 C_9 transition are verified, while unrestricted R_3(C_9)<=33 remains open.