A network can dodge single-color triangles for much longer
How large can a multicolored network become before a one-color triangle is forced?
Color every connection in a complete network with one of k colors. How large can the network become before some triangle is forced to use one color on all three sides? The claimed construction makes the safe size grow faster than Ck for every fixed C. 1manuscript
The object being measured
Consider a complete graph: a set of vertices with an edge between every pair. Color each edge with one of k colors. A monochromatic triangle is a set of three vertices whose three connecting edges all have the same color.
With two colors, a five-vertex graph can still avoid such a triangle, but a six-vertex graph cannot. More colors postpone the forcing threshold. Rk(3) is the first vertex count at which every k-coloring contains a monochromatic triangle.
To prove Rk(3) is large, you do not inspect every coloring. You build one enormous coloring with no monochromatic triangle. The paper’s central achievement is a recursive recipe whose effective exponential base grows with k. 1manuscript
A saturated matrix gives two fixed maps. For every pair of label words, some coordinate makes one endpoint’s label predictable from the other.
What mathematicians knew before
Small triangle-free colorings could be combined through product constructions. Chung, Exoo, and others obtained progressively larger examples. 3Chung 4Exoo But repeating any fixed construction gives only a fixed exponential base: roughly Ck for one constant C. Before this work, the manuscript reports a best lower bound of 380k/5 − O(1). 1manuscript
The upper bound was radically larger—on the scale of k!, which is roughly kk after ignoring lower-order factors. The gap left a qualitative question: is the lower bound merely exponential, or does its base itself grow? Graham, Rothschild, and Spencer recorded the superexponential-growth question in 1990. 5Graham
A fixed product cannot answer it. If one safe object yields base C, tensoring it a hundred times still yields base C. The construction needed a new source of combinatorial gain at every stage while safely reusing colors. 2walkthrough
Technical layer · exponential versus superexponential
A sequence ak is exponential if it behaves like Ck for a fixed C. Its kth root then stays near C. It is superexponential when ak1/k grows without bound.
The classical product inequality makes the limit of Rk(3)1/k exist, possibly at infinity. The theorem proves that the limit is indeed infinity. 1manuscript
The first idea: blocks indexed by missing colors
The construction is recursive. Each new block receives a palette P—not the colors it uses internally, but colors deliberately missing from it. For two blocks P and Q, every cross edge uses a color in the symmetric difference P △ Q: present at one block and missing at the other. 7manuscript
This already kills a triangle spread across three blocks. One color would have to lie in P △ Q, Q △ R, and P △ R simultaneously. But three yes/no membership bits cannot be pairwise different. 7manuscript
It does not kill a triangle using two vertices in one block and one outside. Two matching cross edges might still share the color of the internal edge. This is the subtle failure that forces a stronger invariant. 2walkthrough
Astra’s move: preserve proper labels, not just triangle-freeness
At recursive stage j, require every single-color graph to have a proper vertex labeling with at most j + 1 labels. If two same-colored cross edges enter one active block, the rule forces their internal endpoints into the same proper-label class. Their connecting internal edge therefore cannot have that color. 7manuscript
The forcing rule comes from a saturated matrix. One fixed matrix produces maps f and g such that, for every pair of label words, some coordinate lets one endpoint’s label be predicted from the other. The ingredient comes from earlier hat-guessing and zero-error list-decoding work; its application inside this palette-separated Ramsey recursion is the new use claimed here. 6Alon
Separated palette families ensure every ordered block pair has enough usable colors in each direction. The coordinate cover chooses one of those already available colors and fixes the active endpoint’s proper label. Thus the recursion reuses colors without losing control of two-block triangles. 7manuscript
The triangle audit
- All three vertices in one block: safe by the previous recursive stage.
- Two vertices in one block: if the cross-edge color is missing there, the internal edge cannot use it; if active, the forcing rule gives both vertices the same proper label, so the internal edge still cannot use it.
- Three different blocks: one color cannot belong to all three pairwise symmetric differences. 7manuscript
The proper-label invariant also survives into the next stage: active blocks keep their old labels, while every block missing color c receives one new common label. That is why the construction can continue rather than succeed only once. 7manuscript
Technical layer · why the cube root appears
With stage parameter H, one saturated row needs about H log H symbols. Covering all column choices simultaneously needs about H² log²H rows. Palette separation adds another factor of log H, so the total color count is k ≍ H³ log³H.
Meanwhile, multiplying palette-family sizes across H stages yields about (cH)k vertices. Solving k ≍ H³ log³H for H gives H ≍ k1/3/log k, which becomes the theorem’s growing base. Interpolation between special stage counts is required to cover every integer k ≥ 2. 2walkthrough
Exact result and what remains open
The theorem states that one absolute constant c > 0 satisfies
Rk(3) ≥ (c · k1/3 / log k)k for every k ≥ 2.
Combined with the factorial upper bound, this gives k(1/3−o(1))k ≤ Rk(3) ≤ k(1+o(1))k, summarized as Rk(3) = kΘ(k). 1manuscript
This settles the exponential-versus-superexponential question. It does not determine the leading coefficient of k log k, the best absolute constant, or an exact asymptotic formula. The displayed lower coefficient is 1/3 while the upper coefficient is 1. 1manuscript
A Shannon-capacity consequence
The Ramsey–Shannon correspondence converts a triangle-free k-coloring into a graph G with independence number α(G) = 2 and Shannon capacity at least roughly Rk(3)1/k. Since that root now diverges, graphs with α(G) = 2 can have arbitrarily large Shannon capacity. 8Erdős 9Alon
Equivalently, the largest zero-error message set in one use does not place any universal ceiling on the best per-use zero-error rate after many combined uses. 1manuscript
Is the claim overhyped?
The qualitative breakthrough is real if the proof survives independent scrutiny: the lower bound crosses from fixed-base exponential to superexponential and establishes the broad k-to-the-k scale. It is not an exact Ramsey-number formula.
“Rₖ(3) grows superexponentially.”
Yes. The theorem’s kth-root lower bound is ck1/3/log k, which tends to infinity. 1manuscript
“Rₖ(3) = k^{Θ(k)}.”
Yes as an order-of-growth statement after combining the new lower bound with the classical factorial upper bound. It does not specify the Θ constant. 1manuscript
“The multicolor triangle Ramsey number is now known asymptotically.”
No. A factor-three gap remains between the coefficients 1/3 and 1 in the exponent of k. 1manuscript
“Astra invented the saturated matrix method.”
No. The manuscript credits Alon, Ben-Eliezer, Shangguan, and Tamo, building on earlier zero-error list decoding. The claimed novelty is the palette-separated Ramsey application. 6Alon
“The result is formally and independently validated.”
The Lean file states the all-color lower bound, divergent root, and k log k scale. 10formal artifact The repository labels its review “agent-reviewed,” which is not the same as independent specialist peer review. 11formal artifact
Full bibliography
11 fully annotated sources
- 01 · primary manuscript
OpenAI. Super-exponential lower bounds for R(3,…,3) — Chapter 9, pp. 227–229, Theorem 1.1 and §1.1 (PDF pp. 229–231). Defines Rₖ(3), states the lower bound, historical comparison, Shannon consequence, and proof outline. ↩
- 02 · reasoning walkthrough
OpenAI. Multicolor Ramsey Theory — Chapter 10, §§10.1–10.6, PDF pp. 46–49. Explains why fixed products fail, the stronger invariant, saturated matrix, palette packing, recursion, and scale optimization. ↩
- 03 · peer-reviewed predecessor
Fan Chung. On the Ramsey numbers N(3,3,…,3;2) — Discrete Mathematics 5 (1973), pp. 317–321. An early multicolor triangle-Ramsey lower-bound construction. ↩
- 04 · peer-reviewed predecessor
Geoffrey Exoo. A lower bound for Schur numbers and multicolor Ramsey numbers — Electronic Journal of Combinatorics 1 (1994), Research Paper 8. One of the fixed-base lower-bound constructions preceding the new result. ↩
- 05 · authoritative reference
Ronald Graham, Bruce Rothschild, and Joel Spencer. Ramsey Theory, second edition — Wiley, 1990, p. 146. Records the question of whether the multicolor triangle Ramsey number grows superexponentially. ↩
- 06 · peer-reviewed predecessor
Noga Alon, Omri Ben-Eliezer, Chong Shangguan, and Itzhak Tamo. The hat guessing number of graphs — Journal of Combinatorial Theory, Series B 144 (2020), Lemmas 3.4 and 4.1. Source of the saturated-matrix and coordinate-covering ingredients adapted by the manuscript. ↩
- 07 · primary manuscript
OpenAI. Super-exponential lower bounds for R(3,…,3) — Chapter 9, Lemmas 2.1–2.3 and Proposition 3.1 (PDF pp. 232–234). Proves matrix saturation, palette packing, the recursive coloring, and the three-case triangle audit. ↩
- 08 · peer-reviewed predecessor
Paul Erdős, Robert McEliece, and Herbert Taylor. Ramsey bounds for graph products — Pacific Journal of Mathematics 37 (1971), pp. 45–46. Provides the graph-product connection underlying the Ramsey–Shannon correspondence. ↩
- 09 · peer-reviewed predecessor
Noga Alon and Alon Orlitsky. Repeated communication and Ramsey graphs — IEEE Transactions on Information Theory 41 (1995), §II-A. Makes the Shannon-capacity connection explicit. ↩
- 10 · formal certificate
OpenAI. MulticolorTriangleRamsey.lean — theorems allColourPaletteRamsey_exponential_bound_sharp, triangleRamseyNumber_log_isTheta, and divergentRamseyRoot. Formal statements cover the all-color lower bound, k log k logarithmic scale, and divergent kth root. ↩
- 11 · formal certificate
OpenAI. Formalization metadata — review.status and project.status.main_results, entry “Multicolor triangle Ramsey numbers”. The repository describes its review status as “agent-reviewed.” ↩