Ramsey theory · extremal graph theory
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.
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.
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.
| Result | Label | Scope and caveat |
|---|---|---|
| F(3,k) ≥ maxt C(k,t)2k−t; rate exactly 3 (Thm 3.1) | Proved | All k; construction verified mechanically to K1792 |
| F(j,k) ≥ jk/(2k+2)dj; rate exactly j (Cor 4.4) | Proved | Self-contained for j ≤ 4; j ≥ 5 cites a lemma not read here |
| Antichain palettes cannot beat maxt C(k,t)2k−t (LYM) | Proved | A barrier for this family of constructions only |
| F(3,3) = 14 | Certified | Witnesses + DRUP refutation of n = 15, checker-verified |
| F(3,4) = 41 | Certified | Cube-and-conquer over a certified census; 37 DRUP proofs, 380 MB, not committed (hashes are) |
| F(4,3) = 16 | Certified | Witness; the ≤ 16 side is r3(3) = 17, cited (secondary) |
| F(3,5) ≥ 122, F(3,6) ≥ 365, F(4,4) ≥ 44 | Certified | Witnesses verified from the definition; upper bounds unknown |
| No circulant witness for F(4,4) ≥ 45; none for K46, K50, K51 | Certified | SAT verdicts without proof logs; "no circulant" is not "no witness" |
| Sawin's question, lim F(j,k)/jk | Open. Not answered here. | |
| Wiesner's conjecture for j = 3 | Open. Exact at k = 3, 4; achievable at k = 5, 6; never proved. | |
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.
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.
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
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.
| Cell | Value | Lower bound from | Upper bound from | Label |
|---|---|---|---|---|
| F(3,3) | 14 | three witnesses, verified from the definition | SAT refutation of n = 15, 8,366-line DRUP proof checked by rup_check | Certified |
| F(3,4) | 41 | three witnesses | cube-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) | 16 | witness | r3(3) = 17 (Greenwood–Gleason 1955, secondary) | Certified |
| F(3,5) | ≥ 122 | two witnesses; E5 and a circulant | unknown; 123 undecided | Certified (bound) |
| F(3,6) | ≥ 365 | E6 coloured by SAT in 238 s, verified over all 8,038,030 triples | unknown | Certified (bound) |
| F(4,4) | ≥ 44 | circulant | unknown; no circulant witness at 45 | Certified (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.
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:
| k | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Wiesner's value (3k+1)/2 | 2 | 5 | 14 | 41 | 122 | 365 |
| F(3,k), known | 2 | 5 | 14 | 41 | ≥ 122 | ≥ 365 |
| Theorem 3.1's bound | 2 | 4 | 12 | 32 | 80 | 240 |
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.
| Script | What it does | Cost |
|---|---|---|
code/fjk_sat.py j k n | SAT: is F(j,k) ≥ n? (type formulation, CaDiCaL); writes the witness | 0.1 s at (3,3,15); 0.2 s at (3,4,41) |
code/antichain.py K t out.bin | The Theorem 3.1 construction as a dense matrix, fed to verify_colouring.c | seconds; verified to K1792 |
code/blockconstruct.py | The Theorem 4.2 step j = 3 → 4 with the (3,2) gadget | seconds |
code/fixed_sat_big.py 6 0 | Colours the even-weight set E6, 365 vertices, 10.9 M clauses | 45 s build + 238 s solve |
code/enum_certified.py 3 3 14 | The 14-set census with Glucose + DRUP; the final UNSAT proof certifies completeness | 68 s + 4 min rup_check |
code/cube42.py --prove | The 37 cubes of the F(3,4) ≤ 41 refutation, with DRUP proofs | 228 s CaDiCaL / 167 s Glucose |
code/circ_sat.py n k j | Circulant witnesses on Zn with explicit proper colourings | < 5 s for n ≤ 122 |
code/verify_witness.py, code/verify_colouring.c | From-definition checkers, sharing no code with the search | instant |
Run from inside conjectures/chromatic-ramsey/.