Fabian Arevalo

Ramsey theory · extremal graph theory

Chromatic Ramsey numbers: the growth rate of F(3,k) is exactly 3

A construction that raises the exponential rate of Sawin's F(3,k) from 23/2 to the trivial ceiling 3, the same for every fixed j, and the first exact values beyond F(2,k) = 2k: F(3,3) = 14, F(3,4) = 41, F(4,3) = 16.
September 6, 2026 · session of the Matematica research log · code, witnesses and certificates in conjectures/chromatic-ramsey/

Start here — no maths required

Take n people and draw a line between every pair of them, so every pair is joined. Now hand out k coloured pens and colour each line. The classic Ramsey question asks how big n can get before some three people are forced to have all three of their lines in the same colour.

Will Sawin asked a stricter version. Colour the lines with k pens so that (a) no three people form a triangle in a single colour, and (b) each colour, looked at on its own, is simple: you could sort everyone into just j groups so that no line of that colour ever runs inside a group. Call the largest workable n the number F(j,k).

With j = 2 the answer is exactly 2k, and that is easy. With j = 3 nobody knew whether the answer grows like 3k, which is the obvious ceiling, or like something distinctly smaller: the best construction on record only reached about 2.83k. And no value of F(3,k) had ever been computed. Below is the smallest one, worked out here: fourteen people, three pens.

Show
Fourteen people, three pens, and no way to do it with fifteen. The colouring is a circulant: label the fourteen people 0…13 around a circle and give the line between two of them a pen determined only by how far apart they sit. Pen 1 takes distances {1, 4, 7}, pen 2 takes {2, 3}, pen 3 takes {5, 6}. Isolate a pen and the vertices are drawn with the three-group sorting that makes it simple: filled, hollow, and half-filled. Everything in the readout is recomputed in your browser from the difference classes, including the triangle count and the check that no line runs inside a group. The upper bound, that fifteen is impossible, is not something a picture can show: it is a SAT refutation with a machine-checked proof, described in section 4.

What this note adds

  1. The growth rate is the obvious ceiling after all. A construction gives F(3,k) ≥ 3k/(k+1), so F(3,k)1/k → 3. The previous record rate was about 2.83. The construction is half a page: split the people into blocks indexed by the small subsets of the pen set, put a binary cube inside each block, and colour a line between two blocks by comparing one sign from each. Checked mechanically up to 1,792 people with 8 pens.
  2. The same for every j. F(j,k) ≥ jk/poly(k), hence rate exactly j. Self-contained for j ≤ 4; beyond that it leans on a lemma quoted from elsewhere.
  3. The first exact values. F(3,3) = 14 and F(3,4) = 41, both with machine-checked refutations of the next value up, and F(4,3) = 16. Before this, only the trivial family F(2,k) = 2k was known.
  4. Wiesner's guess is right where it can be checked for three groups, and wrong for four. A conjecture posted in the comments predicts a formula in Stirling numbers. For j = 3 it gives (3k+1)/2, which is exactly right at k = 3 and k = 4 and achievable at k = 5 and 6. At j = 4, k = 3 it predicts 15 and the truth is 16.
  5. And a barrier explaining why the gap is hard to close. No construction of the kind used here can beat maxt C(k,t)2k−t, which decays like 3k/√k. Reaching Wiesner's density of one half needs nested blocks, not the antichain the construction uses.

What this does not do: answer Sawin's actual question, which is about the constant lim F(j,k)/jk, not the rate. The loss here is polynomial and the question is untouched. Figure 2 is the picture of exactly that gap.

AbstractSummary of results

Will Sawin (MathOverflow 513849, 2 August 2026) defines F(j,k) as the largest n such that the edges of Kn can be k-coloured with every colour class triangle-free and vertex j-colourable, notes F(2,k) = 2k and the trivial bounds F(j,k) ≤ jk, F(j,k+1) ≤ j·F(j,k), and asks whether limk F(j,k)/jk = 0 for some j. In the comments Fabius Wiesner conjectures F(j,k) ≥ Σi≤j S(k+1,i) "based on very few numerical tests"; Sawin observes this would give r3(k) ≥ Bk+1. No value of F beyond F(2,k) had been computed anywhere.

We prove F(3,k) ≥ C(k,t)·2k−t for every t ≤ k, hence F(3,k) ≥ 3k/(k+1) and F(3,k) ≥ (1+o(1))·3k·3/(2√(πk)): the exponential growth rate of F(3,k) is exactly 3, where the best rate on record for three-colourable classes was 23/2 ≈ 2.828. More generally F(j,k) ≥ jk/(2k+2)dj for every fixed j, so lim F(j,k)1/k = j for all j. These settle the rate but not Sawin's constant: the loss is polynomial. We also compute the first exact values, F(3,3) = 14, F(3,4) = 41, F(4,3) = 16, with the lower bounds F(3,5) ≥ 122, F(3,6) ≥ 365, F(4,4) ≥ 44.

ResultLabelScope and caveat
F(3,k) ≥ maxt C(k,t)2k−t; rate exactly 3 (Thm 3.1)ProvedAll k; construction verified mechanically to K1792
F(j,k) ≥ jk/(2k+2)dj; rate exactly j (Cor 4.4)ProvedSelf-contained for j ≤ 4; j ≥ 5 cites a lemma not read here
Antichain palettes cannot beat maxt C(k,t)2k−t (LYM)ProvedA barrier for this family of constructions only
F(3,3) = 14CertifiedWitnesses + DRUP refutation of n = 15, checker-verified
F(3,4) = 41CertifiedCube-and-conquer over a certified census; 37 DRUP proofs, 380 MB, not committed (hashes are)
F(4,3) = 16CertifiedWitness; the ≤ 16 side is r3(3) = 17, cited (secondary)
F(3,5) ≥ 122, F(3,6) ≥ 365, F(4,4) ≥ 44CertifiedWitnesses verified from the definition; upper bounds unknown
No circulant witness for F(4,4) ≥ 45; none for K46, K50, K51CertifiedSAT verdicts without proof logs; "no circulant" is not "no witness"
Sawin's question, lim F(j,k)/jkOpen. Not answered here.
Wiesner's conjecture for j = 3Open. Exact at k = 3, 4; achievable at k = 5, 6; never proved.

Section 1The question, and what was known

A (j,k)-colouring of Kn is an edge colouring in k colours in which every colour class is triangle-free and has chromatic number at most j. F(j,k) is the largest n admitting one. Three facts are immediate and are recorded here for completeness: F(j,k+l) ≥ F(j,k)F(j,l) (so lim F(j,k)/jk exists by Fekete), F(j,k) ≤ jk, and F(j,k) ≤ 2jk−1.

Before this note the state was: F(2,k) = 2k exactly, and for three-colourable classes a construction with exponential rate 23/2, from the palette recursion in the OpenAI Ten Advances chapter as expounded by Morris (Theorem 2.1 there, read in full). No exact value of F(j,k) with j ≥ 3 appears anywhere.

Section 2The rate for three-colourable classes is exactly 3

Theorem 3.1

For every t ≤ k, F(3,k) ≥ C(k,t)·2k−t. Consequently F(3,k) ≥ 3k/(k+1) and F(3,k) ≥ (1+o(1))·3k·3/(2√(πk)), so lim F(3,k)1/k = 3. Proved

The construction takes one block for each t-subset P of the colour set [k], and inside that block a binary cube {±1}[k]∖P coloured by first difference. A cross edge between u in block P and v in block Q gets colour a = min(Q∖P) if ua = vb, and b = min(P∖Q) otherwise.

The point that makes it work, and the reason the palette recursion had been losing a factor, is that the "two-sided coordinate cover" the recursion needs is trivial for binary labels: take f = id and g = −id. With binary labels every t-subset can serve as a palette with no Ramsey-type loss, which is exactly the step that was previously paid for.

Inside a block only two labels occur per colour, so a monochromatic triangle would need all three vertices in one block with the same first difference, impossible. Between blocks the colour is chosen so that the active endpoint's label is determined by the other endpoint, which kills the mixed triangles. Each class is 3-colourable by construction. The whole thing was verified mechanically by antichain.py feeding verify_colouring.c, up to K1792 with 8 colours, which is maxt C(8,t)28−t.

Remark 3.2 — the LYM barrier

Any construction of this shape, in which the palettes form an antichain, has at most maxt C(k,t)2k−t vertices, by the LYM inequality. That quantity is Θ(3k/√k), so no antichain construction reaches a constant fraction of 3k. Getting to Wiesner's density of one half needs nested palettes, which is exactly what the even-weight set has. Proved

Section 3Every fixed number of groups

Corollary 4.4

F(j,k) ≥ jk/(2k+2)dj with d2 = 0, d3 = 1, d4 = 3; hence lim F(j,k)1/k = j for every j. Proved

Palettes with pairwise |P∖Q| ≥ s come from power-sum residue classes, and saturated maps of dimension s do the cross colouring. The j = 3 → 4 step uses an explicit nine-entry gadget found by SAT, checked on K56 with 6 colours and K98 with 7 and 8.

Caveat. For j ≥ 5 the corollary depends on the saturated-map lemma of the OpenAI Ten Advances chapter (Lemma 2.2), attributed there to Alon, Ben-Eliezer, Shangguan and Tamo, JCTB 144 (2020). That JCTB paper was not read here; the citation is secondary. For j ≤ 4 everything above is self-contained.

Section 4The first exact values

CellValueLower bound fromUpper bound fromLabel
F(3,3)14three witnesses, verified from the definitionSAT refutation of n = 15, 8,366-line DRUP proof checked by rup_checkCertified
F(3,4)41three witnessescube-and-conquer: the layer x4 = 0 of a 42-set must be one of the 33,831 colourable 14-sets of [3]3 (census completeness carries a 1,529,304-line DRUP proof), i.e. one of 37 orbit representatives, and all 37 cubes are UNSAT with checked DRUP proofs (228 s CaDiCaL / 167 s Glucose)Certified
F(4,3)16witnessr3(3) = 17 (Greenwood–Gleason 1955, secondary)Certified
F(3,5)≥ 122two witnesses; E5 and a circulantunknown; 123 undecidedCertified (bound)
F(3,6)≥ 365E6 coloured by SAT in 238 s, verified over all 8,038,030 triplesunknownCertified (bound)
F(4,4)≥ 44circulantunknown; no circulant witness at 45Certified (bound)

Every witness is checked from the definition by code that shares nothing with the search: the edge colouring is read back, each class is tested for triangles, and each class's own vertex colouring is tested for properness. The K14 and K41 witnesses, and the 365-vertex one, were re-verified independently while this page was written.

Where the certificates are. The F(3,3) ≤ 14 DRUP proof is committed. The two large proof collections behind F(3,4) ≤ 41, the 109 MB census proof and the 380 MB cube collection, are not in the repository; their SHA-256 hashes are, and the scripts regenerate them. The circulant non-existence statements are SAT verdicts without proof logs, which is a weaker certificate and is labelled as one.

Section 5Wiesner's conjecture, and where the gap lives

Wiesner's comment conjectures F(j,k) ≥ Σi≤j S(k+1,i), Stirling numbers of the second kind. For j = 3 that sum is (3k+1)/2. Evaluating both sides:

k123456
Wiesner's value (3k+1)/2251441122365
F(3,k), known251441≥ 122≥ 365
Theorem 3.1's bound24123280240

So the conjecture is exact at every cell where the exact value is known for j = 3, and its value is achievable at k = 5 and 6, realised by the even-weight set Ek, the ternary words with an even number of 2's. At j = 4, k = 3 the sum is 15 and the truth is 16, so the conjecture is a strict lower bound there, not an identity. It is not a theorem and this page does not present it as one, nor as "verified": exact agreement in four cells is evidence, not proof.

The SAT-found extremal sets at k = 3 resemble E3 exactly in their line, plane and layer profile, but E3 is only one of 37 inequivalent extremal 14-sets, so there is no uniqueness to lean on.

The gap that is open, in one picture. All three series are the ratio F(3,k)/3k. The dots are the known values and lower bounds (measurement, exact); the flat line is Wiesner's density one half, which those values sit on; the falling curve is what Theorem 3.1 proves, maxt C(k,t)2k−t/3k, computed live from the formula and decaying like 1/√k. Sawin's question is whether the true ratio goes to zero. The known values say it has not started to; the proved curve is compatible with either answer. Closing the space between the two lines is the whole problem, and the LYM barrier of Remark 3.2 says no construction of the kind used here can do it.

Section 6What stays open

  1. Sawin's actual question. Whether lim F(j,k)/jk = 0 for some j. The theorems here settle the exponential rate and lose a polynomial factor, so the question is untouched.
  2. Wiesner's j = 3 conjecture, which would give lim F(3,k)/3k ≥ 1/2. Every local colouring rule tried for Ek failed; the failures are documented in the note. The LYM barrier says the antichain family cannot get there.
  3. F(3,5) ∈ {122, 123} and F(4,4) ∈ [44, 61]. "No circulant witness" is not "no witness".
  4. A saturated-map gadget for (4,3), which would make j = 5 self-contained. The SAT search did not solve it in five minutes.

Section 7Reproducing this

ScriptWhat it doesCost
code/fjk_sat.py j k nSAT: is F(j,k) ≥ n? (type formulation, CaDiCaL); writes the witness0.1 s at (3,3,15); 0.2 s at (3,4,41)
code/antichain.py K t out.binThe Theorem 3.1 construction as a dense matrix, fed to verify_colouring.cseconds; verified to K1792
code/blockconstruct.pyThe Theorem 4.2 step j = 3 → 4 with the (3,2) gadgetseconds
code/fixed_sat_big.py 6 0Colours the even-weight set E6, 365 vertices, 10.9 M clauses45 s build + 238 s solve
code/enum_certified.py 3 3 14The 14-set census with Glucose + DRUP; the final UNSAT proof certifies completeness68 s + 4 min rup_check
code/cube42.py --proveThe 37 cubes of the F(3,4) ≤ 41 refutation, with DRUP proofs228 s CaDiCaL / 167 s Glucose
code/circ_sat.py n k jCirculant witnesses on Zn with explicit proper colourings< 5 s for n ≤ 122
code/verify_witness.py, code/verify_colouring.cFrom-definition checkers, sharing no code with the searchinstant

Run from inside conjectures/chromatic-ramsey/.