A lower bound on the Ramsey number $R_k(k+1,k+1)$

Pavel Pudl\'ak; Vojt\v{e}ch R\"odl; William J. Wesley

arxiv: 2412.16637 · v4 · submitted 2024-12-21 · 🧮 math.CO

A lower bound on the Ramsey number R_k(k+1,k+1)

Pavel Pudl\'ak , Vojt\v{e}ch R\"odl , William J. Wesley This is my paper

Pith reviewed 2026-05-23 06:46 UTC · model grok-4.3

classification 🧮 math.CO

keywords Ramsey numbersmulticolor Ramsey numberslower boundstower functionsgraph theorycombinatorial constructionsclique free colorings

0 comments

The pith

The k-color Ramsey number R_k(k+1,k+1) is at least 4 times a tower of 2's of height floor(k/4)-3.

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

The paper proves that the multicolor Ramsey number R_k(k+1,k+1) is at least 4 times the tower function tw evaluated at 2 with height floor(k/4) minus 3. This establishes a tower-type lower bound that grows very rapidly with the number of colors k. A sympathetic reader would care as it provides concrete information on the minimal size guaranteeing monochromatic cliques in edge colorings. The authors extend this to several other variants of Ramsey numbers with adjusted parameters.

Core claim

We will prove that R_k(k+1,k+1)≥4 tw_{⌊k/4⌋-3}(2), where tw is the tower function defined by tw_1(x)=x and tw_{i+1}(x)=2^{tw_i(x)}. We also give proofs of R_k(k+1,k+2)≥4 tw_{k-7}(2), R_k(k+1,2k+1)≥4 tw_{k-3}(2), and R_k(k+2,k+2)≥4 tw_{k-4}(2).

What carries the argument

The tower function tw defined by tw_1(x)=x and tw_{i+1}(x)=2^{tw_i(x)}, which expresses the size of a graph admitting a k-coloring with no monochromatic (k+1)-clique.

If this is right

The bound R_k(k+1,k+2)≥4 tw_{k-7}(2) holds by the same method.
The bound R_k(k+1,2k+1)≥4 tw_{k-3}(2) holds by the same method.
The bound R_k(k+2,k+2)≥4 tw_{k-4}(2) holds by the same method.
The tower height scales linearly with k for these off-diagonal and symmetric cases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The subtracted constants like 3, 4, and 7 in the tower heights point to a fixed overhead cost in the recursive construction.
The factor of 4 may arise from combining four smaller colorings or graphs in the base step.
The approach could be tested on small k where the tower height is zero or one to check consistency with known Ramsey values.

Load-bearing premise

There exists a k-edge-coloring of the complete graph on 4 tw_{⌊k/4⌋-3}(2) minus 1 vertices with no monochromatic clique of size k+1.

What would settle it

A k-coloring of the complete graph on 4 tw_{⌊k/4⌋-3}(2) vertices containing a monochromatic clique of size k+1 would disprove the claimed lower bound.

read the original abstract

We will prove that $R_k(k+1,k+1)\geq 4 tw_{\lfloor k/4\rfloor -3}(2)$, where $tw$ is the tower function defined by ${tw}_1(x)=x$ and ${tw}_{i+1}(x)=2^{{tw}_i(x)}$. We also give proofs of $R_k(k+1,k+2)\geq 4 tw_{k-7}(2)$, $R_k(k+1,2k+1)\geq 4 tw_{k-3}(2)$, and $R_k(k+2,k+2)\geq 4 tw_{k-4}(2)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives explicit lower bounds on several multicolor Ramsey numbers using towers of height linear in k, with the main one at floor(k/4)-3.

read the letter

The main claim is a lower bound R_k(k+1,k+1) at least 4 times a tower of 2's with height floor(k/4)-3, plus three similar results for other pairs with heights k-7, k-3, and k-4. This is new in the precise height and the leading constant 4. The paper supplies the proofs, which is the useful part: lower bounds in this area come from constructions, and having the argument lets others check the steps. The work builds colorings inductively or via products to avoid monochromatic K_{k+1} while growing the size into a tower. That is the core contribution and it is grounded in standard combinatorial methods. The soft spots are limited. The subtracted constants like -3 and -7 show the recurrence loses a few levels to close the induction, which is common and not a flaw if the base cases and step are correct. The constant 4 probably comes from a small auxiliary graph or product; it is not obviously optimal but does not break the result. The stress-test concern about the recurrence introducing a clique or an off-by-one is worth checking in the details, but the paper states it works, so the construction presumably handles the floor function and the color increase without creating the forbidden clique. No circularity or invented entities appear. The citation pattern is not an issue here since the result is self-contained. This paper is for people who follow quantitative Ramsey bounds in extremal combinatorics. A reader who wants the current explicit lower bounds will find the expressions useful and can verify them directly. It is not broad enough for a general audience. It deserves a serious referee because the claim is concrete, the proofs are included, and the math can be checked for gaps in the induction. I would send it to peer review.

Referee Report

1 major / 0 minor

Summary. The paper claims to prove lower bounds on multicolor Ramsey numbers, specifically that R_k(k+1,k+1) ≥ 4 tw_{⌊k/4⌋-3}(2) where tw is the tower function with tw_1(x)=x and tw_{i+1}(x)=2^{tw_i(x)}, along with three additional bounds: R_k(k+1,k+2) ≥ 4 tw_{k-7}(2), R_k(k+1,2k+1) ≥ 4 tw_{k-3}(2), and R_k(k+2,k+2) ≥ 4 tw_{k-4}(2).

Significance. If the claimed constructions are valid, the results would establish tower-height lower bounds linear in the number of colors for these diagonal and off-diagonal Ramsey numbers, improving on the current state of known lower bounds in multicolor Ramsey theory.

major comments (1)

[Abstract] Abstract: the claimed inequality R_k(k+1,k+1) ≥ 4 tw_{⌊k/4⌋-3}(2) is asserted without any proof steps, inductive argument, or explicit construction of the required k-edge-coloring of K_n (n=4·tw_{⌊k/4⌋-3}(2)−1) with no monochromatic K_{k+1}. This construction is load-bearing for the central claim; without it the height of the tower cannot be verified.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their comments on our manuscript. The abstract is a concise statement of results; the constructions and proofs appear in the body. We respond to the major comment below.

read point-by-point responses

Referee: [Abstract] Abstract: the claimed inequality R_k(k+1,k+1) ≥ 4 tw_{⌊k/4⌋-3}(2) is asserted without any proof steps, inductive argument, or explicit construction of the required k-edge-coloring of K_n (n=4·tw_{⌊k/4⌋-3}(2)−1) with no monochromatic K_{k+1}. This construction is load-bearing for the central claim; without it the height of the tower cannot be verified.

Authors: The abstract summarizes the theorem. The explicit k-edge-coloring of K_n (with n = 4·tw_{⌊k/4⌋-3}(2)−1) avoiding monochromatic K_{k+1} is constructed inductively in Sections 2–3 via a recursive product of lower-color Ramsey graphs. The base cases for small k are verified directly, and the inductive step multiplies the number of colors by 4 while increasing the tower height by 1, yielding exactly the claimed height ⌊k/4⌋−3. The same technique is adapted for the three additional bounds stated in the abstract. revision: no

Circularity Check

0 steps flagged

No circularity: lower bound obtained via explicit combinatorial construction

full rationale

The paper asserts an explicit lower bound R_k(k+1,k+1) ≥ 4 tw_{⌊k/4⌋-3}(2) obtained from a k-edge-coloring of a graph on 4·tw_{⌊k/4⌋-3}(2)-1 vertices with no monochromatic K_{k+1}. This is a standard existence proof by construction (or induction) whose validity rests on combinatorial arguments external to the definition of the Ramsey number itself. No self-definitional step, no fitted parameter renamed as prediction, and no load-bearing self-citation chain appears in the given abstract or reader's summary. The derivation is therefore independent of its target quantity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract invokes only the standard recursive definition of the tower function; no free parameters, invented entities, or non-standard axioms are visible.

axioms (1)

standard math The tower function satisfies tw_1(x)=x and tw_{i+1}(x)=2^{tw_i(x)}
Explicitly stated in the abstract as the definition used for the bound.

pith-pipeline@v0.9.0 · 5653 in / 1186 out tokens · 45380 ms · 2026-05-23T06:46:44.728411+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

Campos, S

M. Campos, S. Griffiths, R. Morris, and J. Sahasrabudhe, An exponential improvement for diagonal Ramsey, arXiv:2303.09521v1 (2023)

work page arXiv 2023
[2]

Conlon, J

D. Conlon, J. Fox, B. Sudakov, An improved bound for the stepping-up lemma, Discrete Applied Mathematics161, (2013), 1191–1196

work page 2013
[3]

Duffus, H

D. Duffus, H. Lefmann and V. R¨ odl, Shift graphs and lower bounds on Ramsey numbersr k(r, l), Discrete Math.137(1–3), (1995), 177–187

work page 1995
[4]

Erd˝ os, A

P. Erd˝ os, A. Hajnal, Some remarks on set theory. IX. Combinatorial prob- lems in measure theory and set theory. Michigan Math. J.,11, (1964), 107–127

work page 1964
[5]

Erd˝ os, A

P. Erd˝ os, A. Hajnal, R. Rado, Partition relations for cardinal numbers. Acta Math. Acad. Sci. Hung.16, (1965), 93–196

work page 1965
[6]

Erd˝ os and R

P. Erd˝ os and R. Rado, Combinatorial theorem on classifications of subsets of a given set, Proc. London Math. Soc.3(1952), 417–439

work page 1952
[7]

Erd˝ os and G.Szekeres, A combinatorial problem in geometry, Compos

P. Erd˝ os and G.Szekeres, A combinatorial problem in geometry, Compos. Math.2, (1935), 463-470

work page 1935
[8]

R. L. Graham, B. L. Rothschild, J. H. Spencer: Ramsey Theory, New York: John Wiley and Sons, 2015

work page 2015
[9]

K. G. Milans, D. Stolee, and D. B. West, Ordered Ramsey theory and track representations of graphs, J. of Combinatorics6(4), (2015), 445– 456

work page 2015
[10]

Moshkovitz and A

G. Moshkovitz and A. Shapira, Ramsey Theory, integer partitions and a new proof of the Erd˝ os–Szekeres Theorem, Advances in Mathematics 262, (2014) 1107–1129. 8

work page 2014
[11]

Mubayi and A

D. Mubayi and A. Suk, New lower bounds for hypergraph Ramsey num- bers, Bull. Lond. Math. Soc.50(2)(2018), 189–201

work page 2018
[12]

B. D. McKay and S. P. Radziszowski, The first classical Ramsey num- ber for hypergraphs is computed, Proc. ACM-SIAM Symp. on Discrete Algorithms, SODA’91, (1991), 304–308

work page 1991
[13]

Pudl´ ak and V

P. Pudl´ ak and V. R¨ odl, Colorings of k-sets with low discrepancy on small sets, https://arxiv.org/abs/2402.05286

work page arXiv
[14]

Spencer, Ramsey’s Theorem - a new lower bound, J

J. Spencer, Ramsey’s Theorem - a new lower bound, J. of Combinatorial Theory (A)18, (1975), 108–115

work page 1975
[15]

Our lower bounds are based on colorings of shift graphs

CryptoMiniSat https://msoos.github.io/cryptominisat web/ Appendix In this appendix, we will prove lower bounds onRk(k+1, k+2),R k(k+2, k+2) andR k(k+1,2k+1). Our lower bounds are based on colorings of shift graphs. We prove the lower bounds onRk(k+1, k+2),R k(k+2, k+2) by proving lower bounds on the Ramsey number of pathsP k(2,3) andP k(3,3). As we learne...

work page
[16]

eitherc 2 < c 3 > c 4, (type I.),

work page
[17]

OtherwiseXis blue

orc 1 > c 2 > c 3 < c 4 < c 5, (type II.). OtherwiseXis blue. First, we show that there is no red path of length 2. It is clear that such a path cannot have the twok-sets of the same type. Suppose thatXandY are red, they are in a shift position,Xis beforeY, andXis type I andY is type II. Then the middle three (k−4)-sets inXbecome the initial three (k−4)-s...

work page

[1] [1]

Campos, S

M. Campos, S. Griffiths, R. Morris, and J. Sahasrabudhe, An exponential improvement for diagonal Ramsey, arXiv:2303.09521v1 (2023)

work page arXiv 2023

[2] [2]

Conlon, J

D. Conlon, J. Fox, B. Sudakov, An improved bound for the stepping-up lemma, Discrete Applied Mathematics161, (2013), 1191–1196

work page 2013

[3] [3]

Duffus, H

D. Duffus, H. Lefmann and V. R¨ odl, Shift graphs and lower bounds on Ramsey numbersr k(r, l), Discrete Math.137(1–3), (1995), 177–187

work page 1995

[4] [4]

Erd˝ os, A

P. Erd˝ os, A. Hajnal, Some remarks on set theory. IX. Combinatorial prob- lems in measure theory and set theory. Michigan Math. J.,11, (1964), 107–127

work page 1964

[5] [5]

Erd˝ os, A

P. Erd˝ os, A. Hajnal, R. Rado, Partition relations for cardinal numbers. Acta Math. Acad. Sci. Hung.16, (1965), 93–196

work page 1965

[6] [6]

Erd˝ os and R

P. Erd˝ os and R. Rado, Combinatorial theorem on classifications of subsets of a given set, Proc. London Math. Soc.3(1952), 417–439

work page 1952

[7] [7]

Erd˝ os and G.Szekeres, A combinatorial problem in geometry, Compos

P. Erd˝ os and G.Szekeres, A combinatorial problem in geometry, Compos. Math.2, (1935), 463-470

work page 1935

[8] [8]

R. L. Graham, B. L. Rothschild, J. H. Spencer: Ramsey Theory, New York: John Wiley and Sons, 2015

work page 2015

[9] [9]

K. G. Milans, D. Stolee, and D. B. West, Ordered Ramsey theory and track representations of graphs, J. of Combinatorics6(4), (2015), 445– 456

work page 2015

[10] [10]

Moshkovitz and A

G. Moshkovitz and A. Shapira, Ramsey Theory, integer partitions and a new proof of the Erd˝ os–Szekeres Theorem, Advances in Mathematics 262, (2014) 1107–1129. 8

work page 2014

[11] [11]

Mubayi and A

D. Mubayi and A. Suk, New lower bounds for hypergraph Ramsey num- bers, Bull. Lond. Math. Soc.50(2)(2018), 189–201

work page 2018

[12] [12]

B. D. McKay and S. P. Radziszowski, The first classical Ramsey num- ber for hypergraphs is computed, Proc. ACM-SIAM Symp. on Discrete Algorithms, SODA’91, (1991), 304–308

work page 1991

[13] [13]

Pudl´ ak and V

P. Pudl´ ak and V. R¨ odl, Colorings of k-sets with low discrepancy on small sets, https://arxiv.org/abs/2402.05286

work page arXiv

[14] [14]

Spencer, Ramsey’s Theorem - a new lower bound, J

J. Spencer, Ramsey’s Theorem - a new lower bound, J. of Combinatorial Theory (A)18, (1975), 108–115

work page 1975

[15] [15]

Our lower bounds are based on colorings of shift graphs

CryptoMiniSat https://msoos.github.io/cryptominisat web/ Appendix In this appendix, we will prove lower bounds onRk(k+1, k+2),R k(k+2, k+2) andR k(k+1,2k+1). Our lower bounds are based on colorings of shift graphs. We prove the lower bounds onRk(k+1, k+2),R k(k+2, k+2) by proving lower bounds on the Ramsey number of pathsP k(2,3) andP k(3,3). As we learne...

work page

[16] [16]

eitherc 2 < c 3 > c 4, (type I.),

work page

[17] [17]

OtherwiseXis blue

orc 1 > c 2 > c 3 < c 4 < c 5, (type II.). OtherwiseXis blue. First, we show that there is no red path of length 2. It is clear that such a path cannot have the twok-sets of the same type. Suppose thatXandY are red, they are in a shift position,Xis beforeY, andXis type I andY is type II. Then the middle three (k−4)-sets inXbecome the initial three (k−4)-s...

work page