pith. sign in

arxiv: 2605.28793 · v3 · pith:BN56EF6Lnew · submitted 2026-05-27 · 🧮 math.CO

Off-diagonal Ramsey numbers

Domagoj Brada\v{c} This is my paper

Pith reviewed 2026-06-29 11:17 UTC · model grok-4.3

classification 🧮 math.CO
keywords Ramsey numbersoff-diagonal Ramsey numberslower boundscliquesindependent setsgraph theory
0
0 comments X

The pith

For fixed s at least 3, r(s,k) is at least on the order of k to the s-1 over (log k) to the 2s-4.

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

The paper proves a lower bound for the off-diagonal Ramsey number r(s,k) when s is fixed at least 3 and k grows large. It establishes that r(s,k) grows at least like k to the power s-1 divided by (log k) to the power 2s-4. This nearly matches the upper bound proved by Erdős and Szekeres in 1935. For s at least 5 the new bound improves the long-standing Spencer lower bound of roughly k to the (s+1)/2 power.

Core claim

We prove that for any fixed s ≥ 3 and k tending to infinity, the off-diagonal Ramsey numbers satisfy r(s, k) ≥ Ω (k^{s-1} / (log k)^{2s-4}), which matches, up to polylogarithmic factors, the upper bound established over 90 years ago by Erdős and Szekeres. For s ≥ 5, this improves the best known lower bound of the form r(s, k) ≥ k^{(s+1)/2 + o(1)}.

What carries the argument

A combinatorial construction producing a graph on the claimed number of vertices with neither an s-clique nor a k-independent set.

If this is right

  • The gap between lower and upper bounds for r(s,k) shrinks to only polylogarithmic factors in k.
  • For every fixed s at least 5 the previous polynomial exponent (s+1)/2 is replaced by the larger exponent s-1.
  • The result holds uniformly for all fixed s at least 3 as k tends to infinity.

Where Pith is reading between the lines

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

  • The same style of construction might extend to related Ramsey quantities such as multicolor or hypergraph versions.
  • An explicit version of the construction could yield new algorithmic results on finding large cliques or independent sets.

Load-bearing premise

A graph exists on that many vertices with no s-clique and no k-independent set.

What would settle it

An explicit graph on fewer vertices with neither an s-clique nor a k-independent set, or a proof that no such graph exists on the claimed number of vertices.

Figures

Figures reproduced from arXiv: 2605.28793 by Domagoj Brada\v{c}.

Figure 1
Figure 1. Figure 1: The forbidden structure H5. The vertical green edges represent edges in F and the diagonal red edges represent edges in G. Lemma 2.6 (e.g. [5, Corollary 9.2.5]). Let G be an (n, d, λ)-graph and let A, B ⊆ V (G). Then, [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
read the original abstract

For positive integers $s$ and $k$, the Ramsey number $r(s,k)$ is the minimum integer $n$ such that any graph on $n$ vertices contains a clique of size $s$ or an independent set of size $k$. We prove that for any fixed $s \ge 3$ and $k$ tending to infinity, the off-diagonal Ramsey numbers satisfy \[ r(s, k) \ge \Omega \left(\frac{k^{s-1}}{(\log k)^{2s-4}} \right), \] which matches, up to polylogarithmic factors, the upper bound established over 90 years ago by Erd\H{o}s and Szekeres. For $s \ge 5,$ this improves the best known lower bound of the form $r(s, k) \ge k^{\frac{s+1}{2} + o(1)}$ which was first established by Spencer in 1977 and has since only seen polylogarithmic improvements.

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

1 major / 2 minor

Summary. The paper proves that for fixed s ≥ 3 and k → ∞ the off-diagonal Ramsey number satisfies r(s,k) ≥ Ω(k^{s-1}/(log k)^{2s-4}), matching the Erdős–Szekeres upper bound up to polylog factors and improving the Spencer 1977 lower bound of k^{(s+1)/2 + o(1)} for s ≥ 5. The proof proceeds via an iterative semi-random construction that produces a graph on the claimed number of vertices with no K_s and no independent set of size k.

Significance. If the central construction and its analysis hold, the result is a major advance in Ramsey theory: it nearly closes the gap for off-diagonal numbers after decades of only polylogarithmic progress. The manuscript supplies an explicit combinatorial argument rather than a reduction to prior bounds.

major comments (1)
  1. [§3] §3 (Construction and analysis): The bound on Pr[a fixed k-set remains independent] is obtained via a product over rounds that treats edge decisions as essentially independent. Vertex deletions in prior rounds correlate the remaining edge probabilities; the manuscript does not quantify the resulting multiplicative error. If this error is (log k)^{Ω(1)}, the union bound over inom{n}{k} sets fails at the claimed n, reducing the exponent back toward the classical regime.
minor comments (2)
  1. [Introduction] The abstract states the result but the introduction could more explicitly contrast the new exponent s-1 with the prior (s+1)/2 threshold.
  2. [§2] Notation for the semi-random process (e.g., the parameter controlling deletion probability per round) is introduced without a consolidated table of constants.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough review and for recognizing the significance of our result on off-diagonal Ramsey numbers. We address the major comment below.

read point-by-point responses

  1. Referee: [§3] §3 (Construction and analysis): The bound on Pr[a fixed k-set remains independent] is obtained via a product over rounds that treats edge decisions as essentially independent. Vertex deletions in prior rounds correlate the remaining edge probabilities; the manuscript does not quantify the resulting multiplicative error. If this error is (log k)^{Ω(1)}, the union bound over \binom{n}{k} sets fails at the claimed n, reducing the exponent back toward the classical regime.

    Authors: The referee correctly identifies a point that requires more explicit justification. In the semi-random process, we control the deletion probabilities so that the expected number of deletions affecting a fixed set is small. The correlation induced is bounded by a factor of exp(O((log log k)/log k)) per round or better, resulting in a total multiplicative factor of (log k)^{o(1)} over all rounds, which can be absorbed into the existing (log k)^{2s-4} term without changing the asymptotic. However, to address the concern directly, we will add a detailed calculation of this error term in a revised §3, making the analysis self-contained. revision: partial

Circularity Check

0 steps flagged

New probabilistic lower-bound construction is self-contained and independent of self-citations or fitted inputs

full rationale

The paper presents a direct combinatorial/probabilistic construction establishing the stated lower bound on r(s,k). No step reduces by definition or fitting to the target quantity; the cited historical results (Erdős-Szekeres, Spencer) are external upper/prior lower bounds and do not form a load-bearing self-citation chain. The derivation chain therefore contains no self-definitional, fitted-prediction, or uniqueness-imported circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper is a proof of an inequality in Ramsey theory; no free parameters or invented entities are apparent from the abstract. The result builds on standard mathematical foundations.

axioms (2)
  • standard math The definition of Ramsey number r(s,k) as the minimal n such that any graph on n vertices contains a clique of size s or an independent set of size k.
    Invoked in the abstract's opening sentence.
  • domain assumption Asymptotics as k tends to infinity with s fixed.
    The bound is stated explicitly in this regime.

pith-pipeline@v0.9.1-grok · 5696 in / 1406 out tokens · 53275 ms · 2026-06-29T11:17:38.603673+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. New Tower-Type Lower Bounds for Hypergraph Ramsey Numbers

    math.CO 2026-06 unverdicted novelty 7.0

    Improves r_k(k+1,k+1) > s_3(⌊k/2⌋-2) for k≥6 and proves s_3(k) ≥ (twr_{k-2}(2))^2 for k≥5, yielding r_k(k+1,k+1) > (twr_{⌊k/2⌋-4}(2))^2 for k≥14.

  2. (Auto)formalization is supposed to be easy: Trellis process semantics for spelling out rigorous proofs

    cs.AI 2026-06 unverdicted novelty 5.0

    Trellis applies process semantics to guide generalist LLM agents through incremental refinement of proofs for reliable Lean autoformalization, shown via a Ramsey theory example.

Reference graph

Works this paper leans on

51 extracted references · 9 canonical work pages · cited by 2 Pith papers · 2 internal anchors

  1. [1]

    A note on Ramsey’s theorem.Canad

    Harvey Leslie Abbott. A note on Ramsey’s theorem.Canad. Math. Bull., 15:9–10, 1972

    1972

  2. [2]

    A note on Ramsey numbers.J

    Miklós Ajtai, János Komlós, and Endre Szemerédi. A note on Ramsey numbers.J. Combin. Theory Ser. A, 29(3):354–360, 1980

    1980

  3. [3]

    Constructive bounds for a Ramsey-type problem.Graphs Combin., 13(3):217–225, 1997

    Noga Alon and Michael Krivelevich. Constructive bounds for a Ramsey-type problem.Graphs Combin., 13(3):217–225, 1997

    1997

  4. [4]

    Sharp bounds for some multicolor Ramsey numbers.Combinatorica, 25(2):125– 141, 2005

    Noga Alon and Vojtěch Rödl. Sharp bounds for some multicolor Ramsey numbers.Combinatorica, 25(2):125– 141, 2005

    2005

  5. [5]

    Spencer.The probabilistic method

    Noga Alon and Joel H. Spencer.The probabilistic method. Wiley Series in Discrete Mathematics and Opti- mization. John Wiley & Sons, Inc., Hoboken, NJ, fourth edition, 2016

    2016

  6. [6]

    A note on multicolour Ramsey numbers and random sphere graphs

    Yamaan Attwa, Albert López Vidal, and Patrick Morris. A note on multicolour Ramsey numbers and random sphere graphs.arXiv preprint arXiv:2602.02155, 2026

    work page arXiv 2026

  7. [7]

    Upper bounds for multicolour Ramsey numbers.J

    Paul Balister, Béla Bollobás, Marcelo Campos, Simon Griffiths, Eoin Hurley, Robert Morris, Julian Sa- hasrabudhe, and Marius Tiba. Upper bounds for multicolour Ramsey numbers.J. Amer. Math. Soc., 39(3):765–780, 2026

    2026

  8. [8]

    A construction for clique-free pseudorandom graphs

    Anurag Bishnoi, Ferdinand Ihringer, and Valentina Pepe. A construction for clique-free pseudorandom graphs. Combinatorica, 40(3):307–314, 2020

    2020

  9. [9]

    The early evolution of theH-free process.Invent

    Tom Bohman and Peter Keevash. The early evolution of theH-free process.Invent. Math., 181(2):291–336, 2010

    2010

  10. [10]

    Dynamic concentration of the triangle-free process.Random Structures Algorithms, 58(2):221–293, 2021

    Tom Bohman and Peter Keevash. Dynamic concentration of the triangle-free process.Random Structures Algorithms, 58(2):221–293, 2021

    2021

  11. [11]

    William G. Brown. On graphs that do not contain a Thomsen graph.Canad. Math. Bull., 9(3):281–285, 1966

    1966

  12. [12]

    An exponential improvement for diagonal Ramsey.Ann

    Marcelo Campos, Simon Griffiths, Robert Morris, and Julian Sahasrabudhe. An exponential improvement for diagonal Ramsey.Ann. of Math. (2), 203(3):869–932, 2026

    2026

  13. [13]

    A polynomial improvement for the odd cycle-complete Ramsey numbers

    Marcelo Campos, Matthew Jenssen, Marcus Michelen, Florian Pfender, and Julian Sahasrabudhe. A polyno- mial improvement for the odd cycle-complete Ramsey numbers.arXiv preprint arXiv:2511.10641, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  14. [14]

    A new lower bound for the Ramsey numbersR(3, k)

    Marcelo Campos, Matthew Jenssen, Marcus Michelen, and Julian Sahasrabudhe. A new lower bound for the Ramsey numbersR(3, k).arXiv preprint arXiv:2505.13371, 2025

    work page arXiv 2025

  15. [15]

    An update on multicolor Ramsey lower bounds

    Marcelo Campos and Cosmin Pohoata. An update on multicolor Ramsey lower bounds.arXiv preprint arXiv:2601.15183, 2026

    work page arXiv 2026

  16. [16]

    A K Peters, Ltd., Wellesley, MA, 1998

    Fan Chung and Ron Graham.Erdős on graphs. A K Peters, Ltd., Wellesley, MA, 1998. His legacy of unsolved problems

    1998

  17. [17]

    Lower bounds for multicolor Ramsey numbers.Adv

    David Conlon and Asaf Ferber. Lower bounds for multicolor Ramsey numbers.Adv. Math., 378:Paper No. 107528, 5, 2021

    2021

  18. [18]

    Recent developments in graph Ramsey theory

    David Conlon, Jacob Fox, and Benny Sudakov. Recent developments in graph Ramsey theory. InSurveys in combinatorics 2015, volume 424 ofLondon Math. Soc. Lecture Note Ser., pages 49–118. Cambridge Univ. Press, Cambridge, 2015

    2015

  19. [19]

    Ramsey numbers and the Zarankiewicz problem.Bull

    David Conlon, Sam Mattheus, Dhruv Mubayi, and Jacques Verstraëte. Ramsey numbers and the Zarankiewicz problem.Bull. Lond. Math. Soc., 56(6):2014–2023, 2024

    2014

  20. [20]

    Some remarks on the theory of graphs.Bull

    Paul Erdös. Some remarks on the theory of graphs.Bull. Amer. Math. Soc., 53:292–294, 1947

    1947

  21. [21]

    A combinatorial problem in geometry.Compositio Math., 2:463–470, 1935

    Paul Erdös and George Szekeres. A combinatorial problem in geometry.Compositio Math., 2:463–470, 1935

    1935

  22. [22]

    The triangle-free process and the Ramsey number R(3, k).Mem

    Gonzalo Fiz Pontiveros, Simon Griffiths, and Robert Morris. The triangle-free process and the Ramsey number R(3, k).Mem. Amer. Math. Soc., 263(1274):v+125, 2020

    2020

  23. [23]

    Graham, Bruce L

    Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer.Ramsey theory. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., New York, second edition, 1990. A Wiley-Interscience Publication

    1990

  24. [24]

    The Turán number of blow-ups of trees.J

    Andrzej Grzesik, Oliver Janzer, and Zoltán Lóránt Nagy. The Turán number of blow-ups of trees.J. Combin. Theory Ser. B, 156:299–309, 2022

    2022

  25. [25]

    Optimizing the CGMS upper bound on Ramsey numbers.arXiv preprint arXiv:2407.19026, 2024

    Parth Gupta, Ndiame Ndiaye, Sergey Norin, and Louis Wei. Optimizing the CGMS upper bound on Ramsey numbers.arXiv preprint arXiv:2407.19026, 2024. 13

    work page arXiv 2024

  26. [26]

    MulticolorRamseynumbersviapseudorandomgraphs.Electron

    XiaoyuHeandYuvalWigderson. MulticolorRamseynumbersviapseudorandomgraphs.Electron. J. Combin., 27(1):Paper No. 1.32, 8, 2020

    2020

  27. [27]

    ImprovingR(3, k)in just two bites.arXiv preprint arXiv:2510.19718, 2025

    Zion Hefty, Paul Horn, Dylan King, and Florian Pfender. ImprovingR(3, k)in just two bites.arXiv preprint arXiv:2510.19718, 2025

    work page arXiv 2025

  28. [28]

    Gaussian random graphs and Ramsey numbers

    Zach Hunter, Aleksa Milojević, and Benny Sudakov. Gaussian random graphs and Ramsey numbers.arXiv preprint arXiv:2512.17718, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  29. [29]

    The Ramsey numberR(3, t)has order of magnitudet2/logt.Random Structures Algorithms, 7(3):173–207, 1995

    Jeong Han Kim. The Ramsey numberR(3, t)has order of magnitudet2/logt.Random Structures Algorithms, 7(3):173–207, 1995

    1995

  30. [30]

    Some constructive bounds on Ramsey numbers.J

    Alexandr Kostochka, Pavel Pudlák, and Vojtech Rödl. Some constructive bounds on Ramsey numbers.J. Combin. Theory Ser. B, 100(5):439–445, 2010

    2010

  31. [31]

    Bounding Ramsey numbers through large deviation inequalities.Random Structures Algorithms, 7(2):145–155, 1995

    Michael Krivelevich. Bounding Ramsey numbers through large deviation inequalities.Random Structures Algorithms, 7(2):145–155, 1995

    1995

  32. [32]

    Krivelevich and Benny Sudakov

    Michael. Krivelevich and Benny Sudakov. Pseudo-random graphs. InMore sets, graphs and numbers, vol- ume 15 ofBolyai Soc. Math. Stud., pages 199–262. Springer, Berlin, 2006

    2006

  33. [33]

    Rousseau, and Wenan Zang

    Yusheng Li, Cecil C. Rousseau, and Wenan Zang. Asymptotic upper bounds for Ramsey functions.Graphs Combin., 17(1):123–128, 2001

    2001

  34. [34]

    Sharper Ramsey lower bounds from refined Gaussian estimates, 2026

    Qizhong Lin and Lin Niu. Sharper Ramsey lower bounds from refined Gaussian estimates, 2026

    2026

  35. [35]

    An exponential improvement for Ramsey lower bounds.Invent

    Jie Ma, Wujie Shen, and Shengjie Xie. An exponential improvement for Ramsey lower bounds.Invent. Math., pages 1–57, May 2026

    2026

  36. [36]

    A clique-free pseudorandom subgraph of the pseudo polarity graph

    Sam Mattheus and Francesco Pavese. A clique-free pseudorandom subgraph of the pseudo polarity graph. Discrete Math., 345(7):Paper No. 112871, 6, 2022

    2022

  37. [37]

    The asymptotics ofr(4, t).Ann

    Sam Mattheus and Jacques Verstraete. The asymptotics ofr(4, t).Ann. of Math. (2), 199(2):919–941, 2024

    2024

  38. [38]

    Medrano, P

    A. Medrano, P. Myers, H. M. Stark, and A. Terras. Finite analogues of Euclidean space.J. Comput. Appl. Math., 68(1-2):221–238, 1996

    1996

  39. [39]

    Morris, Some recent results in Ramsey theory, arXiv:2601.05221 (2026)

    Robert Morris. Some recent results in Ramsey theory.arXiv preprint arXiv:2601.05221, 2026

    work page arXiv 2026

  40. [40]

    A note on pseudorandom Ramsey graphs.J

    Dhruv Mubayi and Jacques Verstraëte. A note on pseudorandom Ramsey graphs.J. Eur. Math. Soc. (JEMS), 26(1):153–161, 2024

    2024

  41. [41]

    Frank P. Ramsey. On a problem of formal logic.Proc. London Math. Soc. (2), 30(4):264–286, 1929

    1929

  42. [42]

    Counting independent sets in graphs.European J

    Wojciech Samotij. Counting independent sets in graphs.European J. Combin., 48:5–18, 2015

    2015

  43. [43]

    An improved lower bound for multicolor Ramsey numbers and a problem of Erdős.J

    Will Sawin. An improved lower bound for multicolor Ramsey numbers and a problem of Erdős.J. Combin. Theory Ser. A, 188:Paper No. 105579, 11, 2022

    2022

  44. [44]

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

    1983

  45. [45]

    Ramsey’s theorem—a new lower bound.J

    Joel Spencer. Ramsey’s theorem—a new lower bound.J. Combinatorial Theory Ser. A, 18:108–115, 1975

    1975

  46. [46]

    Asymptotic lower bounds for Ramsey functions.Discrete Math., 20(1):69–76, 1977/78

    Joel Spencer. Asymptotic lower bounds for Ramsey functions.Discrete Math., 20(1):69–76, 1977/78

    1977

  47. [47]

    Recent progress in Ramsey theory.arXiv preprint arXiv:2503.22094, 2025

    Jacques Verstraete. Recent progress in Ramsey theory.arXiv preprint arXiv:2503.22094, 2025

    work page arXiv 2025

  48. [48]

    An improved lower bound on multicolor Ramsey numbers.Proc

    Yuval Wigderson. An improved lower bound on multicolor Ramsey numbers.Proc. Amer. Math. Soc., 149(6):2371–2374, 2021. 14 A Spencer’s lower bound close to the diagonal Lets→ ∞and suppose thata=o(s). Then, the best lower bound that can be achieved by Spencer’s method [46] using the Lovász local lemma is given by (5), which we restate for convenience. r(s, s...

    2021

  49. [49]

    andP[B T ] = (1−p) ( k 2). For eachs-setS, there are at least s 2 n−s s−2 events of typeAS′ on whichA S depends, and analogously for eachk-setT, there are at least k 2 n−k k−2 events of typeB T ′ thatB T depends on. To apply A.1, in particular we require p( s

  50. [50]

    The right hand side is maximized by takingxA = s 2 n−s s−2 −1 , which implies p( s

    ≤x A(1−x A)( s 2)( n−s s−2) ≤x A exp −xA s 2 n−s s−2 . The right hand side is maximized by takingxA = s 2 n−s s−2 −1 , which implies p( s

  51. [51]

    Rearranging, we have (1 +o(1)) s 2 ns−2/(s−2)!≤p −( s 2), implying n≤(1 +o(1)) s e ·(1/p) (s+1)/2+1/(s−2)

    ≤ s 2 n−s s−2 −1 . Rearranging, we have (1 +o(1)) s 2 ns−2/(s−2)!≤p −( s 2), implying n≤(1 +o(1)) s e ·(1/p) (s+1)/2+1/(s−2). Completely analogously, we obtain n≤(1 +o(1)) s e ·(1/(1−p)) (k+1)/2+1/(k−2), where we used thatk= (1 +o(1))s. Together, these clearly implyp∈[1/4,3/4], so we may drop the terms2/(s−2)and2/(k−2)from the previous equations to get n≤...