pith. sign in

arxiv: 2606.24198 · v1 · pith:MWMS7XIHnew · submitted 2026-06-23 · 🧮 math.CO

New Tower-Type Lower Bounds for Hypergraph Ramsey Numbers

Hanzhi Bai , Longma Du , Xinyu Hu , Ruilong Liu , Guanghui Wang This is my paper

Pith reviewed 2026-06-26 00:05 UTC · model grok-4.3

classification 🧮 math.CO
keywords hypergraph Ramsey numberstower functionsshift numberslower boundscombinatorial constructionsRamsey theory
0
0 comments X

The pith

A refined construction on shift numbers yields stronger tower-type lower bounds for the diagonal hypergraph Ramsey numbers r_k(k+1,k+1).

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

This paper improves the known lower bounds on the k-uniform hypergraph Ramsey numbers r_k(k+1,k+1) for large k. It does so by providing a better lower bound on the auxiliary 3-color shift number s_3(k) and by extending the range where the construction applies. Specifically, the authors overcome a technical obstruction from prior work to show that the Ramsey number exceeds s_3 of roughly k/2 minus 2, and they prove that s_3 itself is at least the square of a tower function of height k-2. These results give explicit tower lower bounds that are taller than what was previously known. Readers interested in Ramsey theory would care because these numbers measure the guaranteed size at which monochromatic structures must appear in colorings, and tower-type growth indicates extremely rapid increase.

Core claim

The authors prove that for k ≥ 6, r_k(k+1,k+1) > s_3(⌊k/2⌋ − 2) by a new combinatorial construction that avoids the obstruction in the Pudlák-Rödl-Wesley approach. They also characterize s_3(k) exactly and show s_3(k) ≥ (twr_{k−2}(2))^2 for k ≥ 5, which implies r_k(k+1,k+1) > (twr_{⌊k/2⌋−4}(2))^2 for k ≥ 14.

What carries the argument

The 3-color shift number s_3(k), defined via colorings of triples that control shifts in larger sets, which serves as the source of the tower lower bounds.

If this is right

  • The Ramsey lower bound applies for all k ≥ 6 rather than a smaller range.
  • s_3(k) grows at least quadratically in the tower function of one lower height.
  • The overall lower bound for the Ramsey number is now a squared tower instead of a single tower.
  • The exact characterization of s_3(k) may allow determining its precise asymptotic growth.

Where Pith is reading between the lines

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

  • If the new construction generalizes, similar improvements could apply to other hypergraph Ramsey problems.
  • The squared tower bound suggests that the true growth rate might involve higher towers or different multipliers.
  • Computational verification for small k could test the characterization of s_3(k).

Load-bearing premise

The new combinatorial construction for the shift number s_3 succeeds in overcoming the specific obstruction that blocked earlier attempts for the range k≥6.

What would settle it

Finding a specific k ≥ 6 where every 2-coloring of the k-subsets of a set of size s_3(⌊k/2⌋-2) contains a monochromatic (k+1)-set would falsify the main inequality.

read the original abstract

The Ramsey number $r_k(s,m)$ is the smallest $N$ such that any red/blue coloring of the $k$-subsets of $[N]$ contains a red $s$-set or a blue $m$-set. For fixed $k$ and $s$, and for sufficiently large $m$, the tower growth rate is determined by the stepping-up lemma, but for $s=m=k+1$ the available stepping-up lemmas do not apply. Fox asked for estimates of $r_k(k+1,k+1)$. Pudl\'ak, R\"odl, and Wesley gave the first tower-type bound: $r_k(k+1,k+1)\ge s_3(\lfloor k/4\rfloor)\ge 4\operatorname{twr}_{\lfloor k/4\rfloor-4}(2)$, where $s_3(k)$ is the $3$-color shift number and $\operatorname{twr}_1(2)=2$, $\operatorname{twr}_{i+1}(2)=2^{\operatorname{twr}_i(2)}$. In this paper, for $k\ge 6$, we improve the lower bound to $r_k(k+1,k+1)> s_3\bigl(\lfloor k/2\rfloor-2\bigr)$ by overcoming an obstruction in their construction. In addition, we give an exact characterization of $s_3(k)$ and, for $k\ge 5$, obtain a new explicit lower bound $s_3(k)\ge(\operatorname{twr}_{k-2}(2))^2$, which improves the result of Pudl\'ak and R\"odl. Consequently, for $k\ge 14$, $r_k(k+1,k+1)>(\operatorname{twr}_{\lfloor k/2\rfloor-4}(2))^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.

Referee Report

0 major / 2 minor

Summary. The paper improves lower bounds on the k-uniform hypergraph Ramsey numbers r_k(k+1,k+1). It shows that for k≥6 the inequality r_k(k+1,k+1)>s_3(⌊k/2⌋−2) holds by means of a new combinatorial construction for the 3-color shift number s_3 that overcomes the obstruction present in the Pudlák–Rödl–Wesley approach; it supplies an exact characterization of s_3(k); and it proves the explicit lower bound s_3(k)≥(twr_{k−2}(2))^2 for k≥5. The resulting bound is r_k(k+1,k+1)>(twr_{⌊k/2⌋−4}(2))^2 for k≥14.

Significance. The results strengthen the tower-type lower bounds of Pudlák–Rödl–Wesley by replacing the floor(k/4) dependence with floor(k/2)−2 and by squaring the tower in the lower bound for s_3. The explicit combinatorial construction and the exact characterization of s_3 constitute the main technical contributions; if they are correct they constitute a measurable advance on a long-standing open problem in hypergraph Ramsey theory.

minor comments (2)
  1. §1, paragraph following the statement of Theorem 1.2: the sentence describing how the new construction evades the Pudlák–Rödl–Wesley obstruction would benefit from a one-sentence pointer to the precise combinatorial property (e.g., the forbidden subconfiguration) that is now avoided.
  2. Definition 2.3 and the subsequent inductive argument for the characterization of s_3(k): the base case k=5 is stated but the verification that the construction meets the exact characterization is only sketched; a short explicit check for this base case would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation of minor revision. No major comments appear in the report, so there are no specific points requiring a point-by-point response.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation proceeds from an explicit new combinatorial construction for the 3-color shift number s_3(k) that overcomes the Pudlák-Rödl-Wesley obstruction, together with an exact characterization of s_3(k). These yield the stated inequalities r_k(k+1,k+1) > s_3(⌊k/2⌋-2) for k≥6 and s_3(k) ≥ (twr_{k-2}(2))^2 for k≥5 by direct combinatorial argument. No step reduces by definition or by fitting to the target quantity; the tower bounds follow from the construction rather than from any self-referential or self-citation load-bearing premise. The paper is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Relies only on standard definitions and properties of Ramsey numbers and shift numbers from prior literature; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Standard combinatorial definitions and properties of hypergraph Ramsey numbers r_k(s,m) and 3-color shift numbers s_3(k).
    Invoked throughout the abstract when stating improvements over prior constructions.

pith-pipeline@v0.9.1-grok · 5877 in / 1262 out tokens · 24474 ms · 2026-06-26T00:05:01.759358+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 2 canonical work pages

  1. [1]

    Ajtai, J

    M. Ajtai, J. Komlós, and E. Szemerédi, A note on Ramsey numbers.J. Combin. Theory Ser. A29 (1980), 354–360

    1980

  2. [2]

    Ajtai, J

    M. Ajtai, J. Komlós, and E. Szemerédi, A dense infinite Sidon sequence.European J. Combin. 2 (1981), 1–11

    1981

  3. [3]

    Bohman and P

    T. Bohman and P. Keevash, The early evolution of theH-free process,Invent. Math.181 (2010), 291–336

    2010

  4. [4]

    Bradač, Nearly tight exponents for off-diagonal Ramsey numbers, arXiv preprint arXiv:2605.28793, 2026

    D. Bradač, Nearly tight exponents for off-diagonal Ramsey numbers, arXiv preprint arXiv:2605.28793, 2026. 10

    Pith/arXiv arXiv 2026

  5. [5]

    Campos, S

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

    2026

  6. [6]

    Campos, M

    M. Campos, M. Jenssen, M. Michelen, and J. Sahasrabudhe, A new lower bound for the Ramsey numbersR(3,k), arXiv preprintarXiv:2505.13371, 2025

    arXiv 2025

  7. [7]

    F. R. K. Chung and R. L. Graham, Erdős on Graphs: His Legacy of Unsolved Problems, A. K. Peters Ltd., Wellesley, MA, 1998

    1998

  8. [8]

    Conlon, J

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

    2013

  9. [9]

    Conlon, J

    D. Conlon, J. Fox and B. Sudakov, Hypergraph Ramsey numbers,J. Amer. Math. Soc.23 (2010), 247–266

    2010

  10. [10]

    Dobák and E

    D. Dobák and E. Mulrenin, Recursive upper bounds for the vertex online Ramsey game with applications to hypergraph Ramsey numbers, arXiv preprintarXiv:2605.16607, 2026

    Pith/arXiv arXiv 2026

  11. [11]

    L. Du, X. Hu, R. Liu and G. Wang, A double-exponential lower bound forr4(5,n ), arXiv preprintarXiv:2604.23986, 2026

    Pith/arXiv arXiv 2026

  12. [12]

    L. Du, X. Hu, R. Liu and G. Wang, A Note on Generalized Erdős-Rogers Problems, arXiv preprintarXiv:2604.02835, 2026

    Pith/arXiv arXiv 2026

  13. [13]

    Duffus, H

    D. Duffus, H. Lefmann, and V. Rödl, Shift graphs and lower bounds on Ramsey numbers rk(l;r).Discrete Mathematics, 137 (1995), 177–187

    1995

  14. [14]

    Erdős and A

    P. Erdős and A. Hajnal, On Ramsey like theorems, problems and results, Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pp. 123–140, Inst. Math. Appl., Southend-on-Sea, 1972

    1972

  15. [15]

    Erdős, A

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

    1965

  16. [16]

    Erdős and H

    P. Erdős and H. Hanani, On a limit theorem in combinatorical analysis,Publ. Math. Debrecen 10 (1963), 10–13

    1963

  17. [17]

    Erdős and R

    P. Erdős and R. Rado, Combinatorial theorems on classifications of subsets of a given set, Proc. London Math. Soc.(3) 2 (1952), 417–439

    1952

  18. [18]

    Erdős and G

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

    1935

  19. [19]

    C. Fan, X. Hu, Q. Lin and X. Lu, New bounds of two hypergraph Ramsey problems, arXiv preprintarXiv:2410.22019, 2024

    arXiv 2024

  20. [20]

    Fan and Q

    C. Fan and Q. Lin, An improved double-exponential lower bound forr4(5,n ), arXiv preprint arXiv:2605.04105, 2026

    Pith/arXiv arXiv 2026

  21. [21]

    Fiz Pontiveros, S

    G. Fiz Pontiveros, S. Griffiths and R. Morris, The triangle-free process and the Ramsey numberR(3,k),Mem. Amer. Math. Soc.263 (2020), no. 1274, 125 pp. 11

    2020

  22. [22]

    R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey Theory, 2nd ed., Wiley– Interscience, New York, 1990

    1990

  23. [23]

    Gupta, N

    P. Gupta, N. Ndiaye, S. Norin, and L. Wei, Optimizing the CGMS upper bound on Ramsey numbers, arXiv preprintarXiv:2407.19026, 2024

    arXiv 2024

  24. [24]

    Hefty, P

    Z. Hefty, P. Horn, D. King and F. Pfender, ImprovingR(3,k )in just two bites, arXiv preprintarXiv:2510.19718, 2025

    arXiv 2025

  25. [25]

    X. Hu, Q. Lin, X. Lu and G. Wang, Phase transitions of the Erdős-Gyárfás function, arXiv preprintarXiv:2504.05647, 2025

    arXiv 2025

  26. [26]

    Hunter, A

    Z. Hunter, A. Milojević and B. Sudakov, Gaussian random graphs and Ramsey numbers, arXiv preprintarXiv:2512.17718, 2025

    Pith/arXiv arXiv 2025

  27. [27]

    F. Kriegel, The distributive, graded lattice ofEL concept descriptions and its neighborhood relation (extended version), LTCS-Report 18-10, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, Dresden, Germany, 2018. https://doi.org/10.25368/2022.245

    work page doi:10.25368/2022.245 2018

  28. [28]

    J. H. Kim, The Ramsey numberR(3,t )has order of magnitudet2/logt ,Random Struct. Algorithms7 (1995), 173–207

    1995

  29. [29]

    Y. Li, C. C. Rousseau and W. Zang, An upper bound for Ramsey numbers,Appl. Math. Lett.17 (2004), 663–665

    2004

  30. [30]

    Lin and L

    Q. Lin and L. Niu, Sharper Ramsey lower bounds from refined Gaussian estimates, arXiv preprintarXiv:2605.25843, 2026

    Pith/arXiv arXiv 2026

  31. [31]

    J. Ma, W. Shen and S. Xie, An exponential improvement for Ramsey lower bounds,Invent. Math.(2026).https://doi.org/10.1007/s00222-026-01421-9

    work page doi:10.1007/s00222-026-01421-9 2026

  32. [32]

    Mattheus and J

    S. Mattheus and J. Verstraëte, The asymptotics ofr(4,t ),Ann. of Math.199 (2024), 919–941

    2024

  33. [33]

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

    2015

  34. [34]

    Moshkovitz and A

    G. Moshkovitz and A. Shapira, Ramsey Theory, integer partitions and a new proof of the Erdős-Szekeres Theorem,Adv. Math.262 (2014), 1107–1129

    2014

  35. [35]

    Mubayi and A

    D. Mubayi and A. Suk, New lower bounds for hypergraph Ramsey numbers,Bull. London Math. Soc.50 (2018), 189–201

    2018

  36. [36]

    Mubayi and A

    D. Mubayi and A. Suk, Off-diagonal hypergraph Ramsey numbers,J. Combin. Theory Ser. B125 (2017), 168–177

    2017

  37. [37]

    Pudlák and V

    P. Pudlák and V. Rödl, Colorings ofk-sets with low discrepancy on small sets,J. Combin. Theory Ser. B178 (2026), 79–103

    2026

  38. [38]

    Pudlák, V

    P. Pudlák, V. Rödl and W. J. Wesley, A lower bound on the Ramsey numberRk(k +1,k +1), Adv. Comb.2026, Paper No. 3, 9 pp. 12

    2026

  39. [39]

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

    1930

  40. [40]

    J. B. Shearer, A note on the independence number of triangle-free graphs.Discrete Math. 46 (1983), 83–87

    1983

  41. [41]

    Spencer, Asymptotic lower bounds for Ramsey functions,Discrete Math.20 (1977), 69–76

    J. Spencer, Asymptotic lower bounds for Ramsey functions,Discrete Math.20 (1977), 69–76

    1977

  42. [42]

    Wigderson, Ramsey theory: lecture notes, 2024.https://ywigderson.math.ethz.ch/ math/static/RamseyTheory2024LectureNotes.pdf

    Y. Wigderson, Ramsey theory: lecture notes, 2024.https://ywigderson.math.ethz.ch/ math/static/RamseyTheory2024LectureNotes.pdf

    2024

  43. [43]

    Zhao, AIM workshop on Graph Ramsey Theory Problem Session,http://aimpl.org/ graphramsey/1/

    Y. Zhao, AIM workshop on Graph Ramsey Theory Problem Session,http://aimpl.org/ graphramsey/1/. Appendix Verification of the feature transitions Fori∈{0,...,11}, put R(i) := (α(i),β(i))andC(i) := (γ(i),δ(i)). We now verify, without omitting any case, the transition lists used in the proof of Lemma 3.3. Step 1: enumeration of the states.Every x = (a0,a 1,a ...