New upper bound for multicolor Ramsey numbers

Gang Yang; Yaping Mao

New upper bound for multicolor Ramsey numbers

T0 review · 0 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Multicolor diagonal Ramsey numbers satisfy a sharper upper bound, with the exponential saving improved by a factor of order $r^7\log^2(2r)$ and the sufficient $k$-range lowered by a factor of order $r^{12}\log^6(2r)$.

desk verdict A substantial and apparently correct improvement of multicolor Ramsey upper bounds, with a clean proof and one external-lemma caveat worth checking. read the letter →

arxiv 2608.01962 v1 pith:ORRNK73R submitted 2026-08-03 math.CO

Gang Yang , Yaping Mao This is my paper · ORCID

classification math.CO MSC 05C5505D1030D15

keywords multicolorRamseynumbersdiagonalbookmethodrootfiltershigher-ordercorrelationrelativeentropyregularizationlemmaupperbounds

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that the diagonal $r$-color Ramsey number $R_r(k)$ satisfies $R_r(k)\le \exp(-c k/(r^2\log^4(2r)))\,r^{rk}$ once $k\ge K r^2\log^6(2r)$, for absolute constants $c,K>0$. The interest is that both the exponential improvement and the range of $k$ now have much better dependence on the number of colors than previous multicolor bounds: the saving in the exponent is larger by a factor of order $r^7\log^2(2r)$, and the sufficient lower bound on $k$ is smaller by a factor of order $r^{12}\log^6(2r)$. The proof introduces a variable-order positive-coefficient root filter, an entire function whose negative-axis decay is $e^{-u\cos(\pi/d)}$ for an integer $d$ that may grow like $\log(2r)$, and uses it to prove a higher-order correlation lemma with tail exponent $1/d$. It then refines the multicolor book method by retaining all preliminary color spines and using a one-coordinate entropy estimate to capture an extra saving $\exp(-t^2/(64k))$ when the preliminary spines are small.

What carries the argument

The central object is the truncated exponential $E_d(z)=\sum_{n\ge0} z^n/(dn)!$, which averages over the $d$-th roots of unity: for $u\ge0$, $E_d(u^d)=d^{-1}\sum_{j=0}^{d-1}e^{u\omega_d^j}$. Its negative-axis decay $|E_d(-u^d)|\le e^{u\cos(\pi/d)}$, paired with the positive-axis growth $E_d(u^d)\ge e^u/(2d)$, turns the ratio $G_{r,d}/H_{r,d}$ built from $H_{r,d}(z)=1+a_{r,d}E_d(z)^2$ and its odd part into a sharp threshold function. The multivariate sum $F_{r,d}(x_1,\ldots,x_r)=\sum_j G_{r,d}(x_j)\prod_{i\ne j}H_{r,d}(x_i)$ has nonnegative Taylor coefficients, so its expectation under independent copies is nonnegative; evaluating it at $L_{r,d}Z_i$ for $Z_i=\langle\sigma_i(U),\sigma_i(U')\rangle$ yields the higher-order correlation bound $\mathbb{P}(Z_i\ge\lambda,\, Z_j\ge-1\ \forall j\ne i)\ge \beta_r\exp(-C_{r,d}(\lambda+1)^{1/d})$. The second mechanism is the retained-spine refinement: all $r$ preliminary cliques $S_i$ and the common reservoir $W$ from the regularization lemma are kept; if $s=\sum_i|S_i|\ge rt/4$ the regularization gain alone wins, and if $s<rt/4$ the distinguished target $k-s_i-t$ lies below the diagonal by an amount of order $t$, so a one-coordinate multinomial entropy estimate gives $R(b_1,\ldots,b_r)\le r^{rk-s-t}e^{-t^2/(64k)}$. The book lemma then builds a color-$i$ spine of size $t$ with page set of size $m$ while compensating the reservoir loss $rt\Xi$.

What would settle it

An $r$-coloring of $K_n$ with $n>\exp(-c k/(r^2\log^4(2r)))\,r^{rk}$ and no monochromatic $K_k$, for some $k\ge K r^2\log^6(2r)$, would disprove Theorem 1.1 directly. The first place to look is whether Lemma 2.1's quantitative reservoir and degree bounds fail at $\eta=\alpha\vartheta/r$, because such a failure would break the proof before the book argument begins.

Watch

Extended reading notes

Core claim

The central claim is a new upper bound for diagonal multicolor Ramsey numbers: there are absolute constants $c,K>0$ such that for every $r\ge2$ and every $k\ge K r^2\log^6(2r)$, one has $R_r(k)\le \exp(-c k/(r^2\log^4(2r)))\,r^{rk}$. Relative to the previously best multicolor bound, whose exponent saving was of order $k/(r^9\log^6(2r))$ under the condition $k\ge C r^{14}\log^{12}(2r)$, this improves the saving by a factor of order $r^7\log^2(2r)$ and lowers the displayed sufficient lower bound on $k$ by a factor of order $r^{12}\log^6(2r)$. The proof achieves this by combining a variable-order root filter, which replaces the square-root tail of earlier correlation estimates by a $1/d$-power tail for an integer $d$ that may grow with $r$, with a retained-spine refinement of the book method, in which all $r$ preliminary monochromatic cliques from the regularization step are kept and the off-diagonal Ramsey problem inside the page set is handled by a one-coordinate multinomial entropy estimate.

Load-bearing premise

The load-bearing input is Lemma 2.1, an imported regularity statement that guarantees the $r$ preliminary color-cliques $S_i$ and a common reservoir $W$ of size at least $((1+\eta)/r)^s n$ with color-$i$ degrees at least $(1/r-\eta)|W|-1$ for every $w\in W$; if those quantitative guarantees failed at the small slack $\eta=\alpha\vartheta/r$ used in Section 5, the page-retention and reservoir estimates of the book argument would collapse.

Editorial extensions

If this is right

For every growing number of colors, the diagonal Ramsey upper bound has saving $\exp(-c k/(r^2\log^4(2r)))$ instead of the previous $\exp(-c k/(r^9\log^6(2r)))$, so the exponent saving is larger by a factor of order $r^7\log^2(2r)$.
The theorem holds already for $k\ge K r^2\log^6(2r)$, which lowers the previously sufficient $k$-range by a factor of order $r^{12}\log^6(2r)$.
With $d=3$ the same proof gives a saving of order $k/(r^3\log^2(2r))$, and with $d=4$ a saving of order $k/(r^{8/3}\log^{4/3}(2r))$, so smaller orders of the root filter yield weaker but still valid bounds.
The parametrized Theorem 1.2 gives a family of bounds indexed by the root-filter order $d$, so the method contains an explicit trade-off between the size of the exponential saving and the required size of $k$.
For fixed small $r$, the paper does not attempt to optimize the numerical base; in particular, the specialized two-color bound remains stronger when $r=2$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the root-filter construction is a template: any positive-coefficient entire function with negative-axis decay $e^{-u\cos(\pi/d)}$ and positive-axis growth $e^u$ should yield a correlation lemma with tail exponent $1/d$, and other filters, such as averages over the $d$-th roots of $-1$, might give different $r$-dependencies.
Editorial inference: the one-coordinate entropy estimate in Lemma 5.2 is stated for the diagonal problem, but the same inequality $R(b_1,\ldots,b_r)\le r^B e^{-t^2/(64k)}$ applies to off-diagonal target vectors, so the retained-spine argument may be reusable for mixed Ramsey numbers.
Editorial inference: the choice $d=\Theta(\log(2r))$ balances factors like $r^{2d/(d-1)}d^{4d/(d-1)}$ against the threshold; a finer optimization over $d$ or a combination of two filters might improve the $r$-dependence further, since the paper does not claim optimality of the absolute constants.
Editorial inference: because the correlation theorem holds for arbitrary Hilbert-space-valued maps $\sigma_i$, it may have applications outside Ramsey theory, for instance wherever one studies simultaneous weak correlation of several vector-valued maps and needs a quantitative clustering conclusion.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline is right: this paper genuinely improves the state of the art for diagonal multicolor Ramsey numbers in the many-color regime. Compared with the Narang–Tang preprint, the saving in the exponent goes from k/(r^9 log^6) to k/(r^2 log^4), and the k-threshold drops from r^14 log^12 to r^2 log^6. That is a large, concrete advance, not a cosmetic one. The two new ingredients—the variable-order root filter and the retained-spine refinement—are not in the cited literature, and the proof shows why they work.

I read Sections 3–5 carefully. The correlation theorem is clean: the positivity argument via tensor products is simple and correct, and the tail estimate with the 1/d exponent is exactly what gives the improved r-dependence. The density-increment lemma and the book lemma are intricate but the bookkeeping closes. I checked the entropy estimate in Lemma 5.2 and the parameter verifications in Lemma 5.4; the inequalities (57)–(63) all hold with the stated choices. I did not find a circular step or a hidden fitting of constants. The proof is internally consistent.

The one soft spot is the imported Lemma 2.1 from Balister et al. The quantitative bounds |W| ≥ ((1+η)/r)^s n and the degree condition are used at the sharp end, with η = αϑ/r tending to 0 as r grows. If that published lemma secretly requires η bounded below by an absolute constant, or requires n to be large relative to some function of η, the application here would be out of regime. The stress-test note found no evidence of such a restriction, and the lemma is published, so this is a verification gap in an external input rather than an internal flaw. It deserves a careful check by the referee but does not undermine the argument as written.

Minor issues: the abstract has a stray "b" after "book method." The proof is long and parameter-heavy, so independent verification (human or formal) would be valuable, but that is a feature of this type of argument, not a defect.

Bottom line: this is a serious, important paper. The central argument holds up on inspection, and the one substantive caveat is about a quoted lemma, not about the authors' reasoning. It should definitely go to peer review. I would bring it to a reading group and would cite it.

Recommendation: accept with minor revisions, after a referee checks Lemma 2.1's hypotheses and the bookkeeping in Lemma 5.4.

Referee Report

0 major / 3 minor

Summary. The paper proves a new upper bound for diagonal multicolor Ramsey numbers. Theorem 1.1 states that there are absolute constants c,K>0 such that for every r≥2 and every k≥K r^2 log^6(2r), one has R_r(k)≤ exp(-c k/(r^2 log^4(2r))) r^{rk}. The proof has two new ingredients: a higher-order correlation lemma based on a positive-coefficient root filter of variable order d (Theorem 3.4), and a retained-spine refinement of the multicolor book method (Theorem 4.2). An entropy estimate for off-diagonal Ramsey numbers (Lemma 5.2) is then used to close the argument. The paper also states a more flexible Theorem 1.2, from which Theorem 1.1 is derived by choosing d≈log(2r).

Significance. If correct, Theorem 1.1 is the strongest known upper bound for diagonal multicolor Ramsey numbers in the many-color regime, improving both the exponent saving and the admissible range of k over the recent results of Balister et al. and Narang and Tang. The proof is explicit and self-contained except for the quoted Erdős–Szekeres regularization lemma from [1]; the algebraic identities and parameter inequalities are checked carefully, and the absolute constants are chosen by existence arguments rather than fitted to the conclusion. The main residual risk is the exact quantitative content of the external Lemma 2.1, on which the later book and reservoir estimates depend.

minor comments (3)

[§3.1–§3.2, §5.1] Several cross-references are incorrect: in the proof of Lemma 3.2, “Theorem 3.1” should be “Lemma 3.1”; in the proof of Lemma 3.3, “Theorem 3.2” should be “Lemma 3.2”; in the proof of Theorem 3.4, “Theorem 3.3(i)” and “Theorem 2.2” should be “Lemma 3.3(i)” and “Lemma 2.2”; and in Lemma 5.1, “Theorem 2.1” should be “Lemma 2.1.”
[§5.2] The application of Lemma 2.1 uses η=αϑ/r, which tends to 0 as r grows, and s up to rt/4 in the small-s case, while the later estimates (73), the page-size check, and the reservoir check rely on the exact displayed constants in (6)–(7). I ask the authors to add a sentence confirming that the quoted form of [1, Lemma 5.2] holds for arbitrary η>0 with no implicit lower bound on η or hidden condition on n beyond the stated hypotheses. This is a verification request rather than a detected internal error.
[Abstract] The abstract contains a stray “.b” at the end of “book method.b”; this should be removed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; the proof is self-contained apart from an external structural lemma that is not target-equivalent.

full rationale

The paper's derivation is built from internal ingredients: the positivity lemma (Lemma 2.2), the higher-order correlation theorem (Theorem 3.4) proven from the root filter E_d, and the book lemma (Theorem 4.2) that assumes the parameterized correlation property G^{(d)}_r(β,C) and then receives it from Theorem 3.4 in the final application. The constants β_r and C_{r,d} are explicit expressions in r and d, and the absolute constants b,c,K are chosen by existence arguments from displayed inequalities, not fitted to the target bound. The only external input is Lemma 2.1, imported from Balister et al. [1, Lemma 5.2]; that lemma supplies preliminary monochromatic spines and a common reservoir with quantitative bounds. It is not authored by the present authors, is not equivalent to the target upper bound, and functions as a background structural result rather than a smuggled form of the conclusion. No self-citation is load-bearing, no uniqueness theorem is invoked, and no known result is renamed. Thus, under the stated criteria, the paper exhibits no circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The proof does not fit any free parameters to data. It uses one imported structural lemma and standard analytic and combinatorial background. No invented entities are introduced.

assumptions (3)

standard math Erdős–Szekeres recursion and multinomial bound R(k1,...,kr) ≤ r^B (Section 2, equations (4)-(5))
Used as the baseline upper bound in the entropy argument and in the final assembly.
standard math Hilbert tensor product positivity lemma (Lemma 2.2)
The proof of the higher-order correlation theorem relies on the identity that the expectation of a product of inner products of independent copies is a norm squared.
domain assumption Erdős–Szekeres regularization lemma of Balister et al. (Lemma 2.1, cited from [1, Lemma 5.2])
Produces the preliminary color-i spines S_i and common reservoir W that the retained-spine argument needs; this is the main imported structural input.

how reviews work

0 comments

Cite this review

Pith. "Pith review of New upper bound for multicolor Ramsey numbers." pith.science (2026). https://pith.science/paper/ORRNK73R

@misc{pith2026260801962,
  author       = {Pith},
  title        = {Pith review of: New upper bound for multicolor Ramsey numbers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ORRNK73R}},
  note         = {Machine review of arXiv:2608.01962}
}

abstract

Let $R_r(k)$ denote the diagonal $r$-color graph Ramsey number. We prove that there exist absolute constants $c,K>0$ such that \[ R_r(k)\le \exp\!\left(-c\frac{k}{r^2\log^4(2r)}\right)r^{rk} \] for every $r\ge2$ and every $k\ge Kr^2\log^6(2r)$. The proof combines a positive-coefficient root filter of variable order with a retained-spine refinement of the multicolor book method.b

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 10 canonical work pages

[1]

Balister, B

P. Balister, B. Bollobás, M. Campos, S. Griffiths, E. Hurley, R. Morris, J. Sahasrabudhe, M. Tiba, Upper bounds for multicolour Ramsey numbers,J. Amer. Math. Soc.39(3) (2026), 765–780

work page 2026
[2]

Campos, S

M. Campos, S. Griffiths, R. Morris, J. Sahasrabudhe, An exponential improvement for diagonal Ramsey,Ann. of Math.203(3) (2026), 869–932

work page 2026
[3]

Conlon, A new upper bound for diagonal Ramsey numbers,Ann

D. Conlon, A new upper bound for diagonal Ramsey numbers,Ann. of Math.170(2) (2009), 941–960

2009
[4]

Conlon, J

D. Conlon, J. Fox, B. Sudakov, Recent developments in graph Ramsey theory, inSurveys in Combinatorics 2015, A. Czumaj, A. Georgakopoulos, D. Král, V. Lozin, O. Pikhurko, eds., London Math. Soc. Lecture Note Ser. 424, Cambridge Univ. Press, Cambridge, 2015, 49–118

work page 2015
[5]

Erdős, Some remarks on the theory of graphs,Bull

P. Erdős, Some remarks on the theory of graphs,Bull. Amer. Math. Soc.53(4) (1947), 292–294

work page 1947
[6]

Erdős, G

P. Erdős, G. Szekeres, A combinatorial problem in geometry,Compositio Math.2 (1935), 463–470

work page 1935
[7]

Gupta, N

P. Gupta, N. Ndiaye, S. Norin, L. Wei, Optimizing the CGMS upper bound on Ramsey numbers, arXiv:2407.19026 [math.CO], 2024

arXiv 2024
[8]

Schrijver Number Quasi-Tensorization and Multicolor Ramsey Bounds via Robust OR Polynomials

I. Narang, Y. Tang, Schrijver number quasi-tensorization and multicolor Ramsey bounds via robust OR polynomials, arXiv:2607.25023 [math.CO], 2026

work page Pith review arXiv 2026

Show all 12 references

[9]

F. P. Ramsey, On a problem of formal logic,Proc. London Math. Soc.(2) 30(1) (1930), 264–286

1930
[10]

Sah, Diagonal Ramsey via effective quasirandomness,Duke Math

A. Sah, Diagonal Ramsey via effective quasirandomness,Duke Math. J.172(3) (2023), 545–567

2023
[11]

Thomason, An upper bound for some Ramsey numbers,J

A. Thomason, An upper bound for some Ramsey numbers,J. Graph Theory12(4) (1988), 509–517

1988
[12]

Wigderson, Upper bounds on diagonal Ramsey numbers (after Campos, Griffiths, Morris, and Sahasrabudhe),Astérisque462 (2025), Exp

Y. Wigderson, Upper bounds on diagonal Ramsey numbers (after Campos, Griffiths, Morris, and Sahasrabudhe),Astérisque462 (2025), Exp. No. 1230, 85–138. 28

2025

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

Balister, B

P. Balister, B. Bollobás, M. Campos, S. Griffiths, E. Hurley, R. Morris, J. Sahasrabudhe, M. Tiba, Upper bounds for multicolour Ramsey numbers,J. Amer. Math. Soc.39(3) (2026), 765–780

work page 2026

[2] [2]

Campos, S

M. Campos, S. Griffiths, R. Morris, J. Sahasrabudhe, An exponential improvement for diagonal Ramsey,Ann. of Math.203(3) (2026), 869–932

work page 2026

[3] [3]

Conlon, A new upper bound for diagonal Ramsey numbers,Ann

D. Conlon, A new upper bound for diagonal Ramsey numbers,Ann. of Math.170(2) (2009), 941–960

2009

[4] [4]

Conlon, J

D. Conlon, J. Fox, B. Sudakov, Recent developments in graph Ramsey theory, inSurveys in Combinatorics 2015, A. Czumaj, A. Georgakopoulos, D. Král, V. Lozin, O. Pikhurko, eds., London Math. Soc. Lecture Note Ser. 424, Cambridge Univ. Press, Cambridge, 2015, 49–118

work page 2015

[5] [5]

Erdős, Some remarks on the theory of graphs,Bull

P. Erdős, Some remarks on the theory of graphs,Bull. Amer. Math. Soc.53(4) (1947), 292–294

work page 1947

[6] [6]

Erdős, G

P. Erdős, G. Szekeres, A combinatorial problem in geometry,Compositio Math.2 (1935), 463–470

work page 1935

[7] [7]

Gupta, N

P. Gupta, N. Ndiaye, S. Norin, L. Wei, Optimizing the CGMS upper bound on Ramsey numbers, arXiv:2407.19026 [math.CO], 2024

arXiv 2024

[8] [8]

Schrijver Number Quasi-Tensorization and Multicolor Ramsey Bounds via Robust OR Polynomials

I. Narang, Y. Tang, Schrijver number quasi-tensorization and multicolor Ramsey bounds via robust OR polynomials, arXiv:2607.25023 [math.CO], 2026

work page Pith review arXiv 2026