pith. sign in

arxiv: 2511.10641 · v2 · submitted 2025-11-13 · 🧮 math.CO

A polynomial improvement for the odd cycle-complete Ramsey numbers

Marcelo Campos , Matthew Jenssen , Marcus Michelen , Florian Pfender , Julian Sahasrabudhe This is my paper

Pith reviewed 2026-05-17 22:06 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C55
keywords Ramsey numbersodd cyclescycle-complete Ramseylower boundsprobabilistic methodextremal graph theorysemi-random graphs
0
0 comments X

The pith

Ramsey numbers r(C_ℓ, K_k) for odd cycles gain an extra polynomial factor in the lower bound when ℓ exceeds 7.

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

The paper proves that for every fixed odd integer ℓ greater than 7, the Ramsey number r(C_ℓ, K_k) satisfies a stronger lower bound than previously known. Specifically, it grows at least as fast as k raised to the power 1 + 1/(ℓ-2) plus a positive term ε_ℓ that depends on ℓ, with the usual o(1) correction as k tends to infinity. This improvement comes from a refined construction that produces larger graphs without containing a cycle of length ℓ or a clique of size k. Readers interested in extremal graph theory would care because the result tightens the known growth rate of these mixed Ramsey numbers and shows that the earlier exponent is not optimal.

Core claim

We prove that for all fixed odd ℓ > 7 there exists ε_ℓ > 0 such that r(C_ℓ, K_k) ≥ k^{1 + 1/(ℓ-2) + ε_ℓ + o(1)} as k → ∞.

What carries the argument

A tuned semi-random graph model whose edge probabilities and deletion steps are chosen to keep the probability of forming a C_ℓ below the threshold that would collapse the size lower bound.

If this is right

  • The previous best lower bound exponent 1 + 1/(ℓ-2) is no longer tight for odd ℓ > 7.
  • The improvement applies uniformly once the cycle length is at least 9.
  • The o(1) term means the extra factor becomes visible for sufficiently large clique size k.

Where Pith is reading between the lines

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

  • Refinements of the same deletion technique might extend the extra factor to some even cycle lengths.
  • The precise threshold where ε_ℓ becomes positive could be lowered with more careful parameter tuning.

Load-bearing premise

The probabilistic construction must succeed in avoiding odd cycles of length ℓ while retaining enough vertices and edges to beat the old exponent.

What would settle it

An explicit calculation or simulation for ℓ = 9 showing that the probability of creating a C_9 in the model exceeds the survival threshold for arbitrarily large k would falsify the claimed ε_ℓ.

read the original abstract

We give a polynomial improvement to the cycle-complete Ramsey numbers \[ r(C_{\ell},K_k) \geq k^{1+1/(\ell- 2) + \varepsilon_{\ell} + o(1)}, \] for all fixed odd $\ell > 7$ with $k \rightarrow \infty$, for some $\varepsilon_{\ell} > 0$.

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 claims a polynomial improvement to the lower bound on the Ramsey number r(C_ℓ, K_k) for fixed odd ℓ > 7: specifically, r(C_ℓ, K_k) ≥ k^{1 + 1/(ℓ-2) + ε_ℓ + o(1)} as k → ∞ for some ε_ℓ > 0. The proof proceeds via a probabilistic (or semi-random) construction of a graph on n vertices with no K_k and no C_ℓ, using an edge-probability tuned to avoid large cliques followed by a deletion phase to remove odd cycles of length ℓ.

Significance. If the error-term control holds, this supplies the first explicit positive ε_ℓ improvement over the classical exponent 1 + 1/(ℓ-2) for these cycle-complete Ramsey numbers when ℓ is odd and greater than 7. Such a polynomial gain is meaningful in extremal graph theory because the previous best lower bounds were of the form k^{1 + 1/(ℓ-2) + o(1)}; the construction is non-circular and directly computes the surviving vertex count from the chosen parameters.

major comments (1)
  1. [construction section] The probabilistic deletion step (construction section): the analysis must exhibit an explicit parameter regime in which the expected number of C_ℓ is driven below 1 while the fraction of vertices or edges removed remains small enough that the surviving n still satisfies n = k^{1 + 1/(ℓ-2) + ε_ℓ + o(1)} with ε_ℓ bounded away from zero. When ℓ is only slightly larger than 7 the cycle-counting terms become comparable to the clique-avoidance terms; if the required deletion probability forces a super-constant loss, the claimed ε_ℓ collapses. A concrete calculation showing that the deletion probability p satisfies p = o(1) uniformly in the relevant range of ℓ would resolve this.
minor comments (2)
  1. Clarify the precise random model (G(n,p) or semi-random) and the exact deletion rule (edge deletion versus vertex deletion) in the opening paragraph of the construction.
  2. Add a short remark comparing the new ε_ℓ with the best previously known o(1) terms for the same range of ℓ.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful and constructive report. The request for an explicit parameter regime in the deletion analysis is well-taken and will be addressed by adding a self-contained lemma that makes the bounds fully quantitative.

read point-by-point responses

  1. Referee: [construction section] The probabilistic deletion step (construction section): the analysis must exhibit an explicit parameter regime in which the expected number of C_ℓ is driven below 1 while the fraction of vertices or edges removed remains small enough that the surviving n still satisfies n = k^{1 + 1/(ℓ-2) + ε_ℓ + o(1)} with ε_ℓ bounded away from zero. When ℓ is only slightly larger than 7 the cycle-counting terms become comparable to the clique-avoidance terms; if the required deletion probability forces a super-constant loss, the claimed ε_ℓ collapses. A concrete calculation showing that the deletion probability p satisfies p = o(1) uniformly in the relevant range of ℓ would resolve this.

    Authors: We agree that greater explicitness is desirable. In the current manuscript the edge probability is set to p = n^{-(ℓ-2)/(ℓ-1) + δ_ℓ} for a small positive δ_ℓ depending only on ℓ; this already ensures that the expected number of K_k is o(1) while the expected number of C_ℓ is O(n^ℓ p^ℓ) = o(n). Deleting one vertex per surviving C_ℓ therefore removes only o(n) vertices in expectation. The resulting loss is absorbed into the o(1) term of the exponent and leaves a positive ε_ℓ that depends only on ℓ. To address the referee’s concern directly we will insert a new lemma (Lemma 3.4 in the revision) that computes the deletion fraction explicitly as a function of ℓ and verifies that it tends to zero for every fixed odd ℓ > 7, including the smallest cases ℓ = 9 and ℓ = 11. The same lemma also records the concrete lower bound on ε_ℓ obtained from the chosen δ_ℓ, confirming that the improvement does not collapse. We therefore view the requested calculation as a clarification rather than a correction of the argument. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit probabilistic construction with direct parameter calculation

full rationale

The paper establishes the lower bound r(C_ℓ, K_k) ≥ k^{1 + 1/(ℓ-2) + ε_ℓ + o(1)} via an explicit random or semi-random graph construction on n vertices. Edge probabilities are chosen to control the expected number of K_k subgraphs, followed by a deletion phase to eliminate C_ℓ copies while preserving a positive fraction of vertices. The resulting n is computed directly from the chosen probabilities and deletion thresholds using standard probabilistic method calculations (expectation and concentration bounds). No step defines the target exponent in terms of itself, fits a parameter to a subset of the Ramsey quantity, or relies on a self-citation chain for the core existence claim. The derivation is self-contained against external probabilistic benchmarks and does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests on standard probabilistic method axioms and counting lemmas for cycles in random graphs; no new free parameters or invented entities are introduced beyond the usual choice of edge probability p = k^{-c} for suitable c.

axioms (1)
  • standard math The probabilistic deletion method preserves the absence of K_k while controlling the expected number of C_ℓ copies.
    Invoked in the construction of the lower-bound graph.

pith-pipeline@v0.9.0 · 5355 in / 1335 out tokens · 28356 ms · 2026-05-17T22:06:55.330988+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

15 extracted references · 15 canonical work pages

  1. [1]

    Bohman and P

    T. Bohman and P. Keevash. The early evolution of theH-free process.Inventiones mathematicae, 181(2):291–336, 2010

    work page 2010

  2. [2]

    Bollob´ as.Random graphs

    B. Bollob´ as.Random graphs. Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2001. 12

    work page 2001

  3. [3]

    Campos, M

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

    work page arXiv 2025

  4. [4]

    Y. Caro, Y. Li, C. C. Rousseau, and Y. Zhang. Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers.Discrete Math., 220(1-3):51–56, 2000

    work page 2000

  5. [5]

    Conlon, S

    D. Conlon, S. Mattheus, D. Mubayi, and J. Verstra¨ ete. Ramsey numbers and the Zarankiewicz problem. Bulletin of the London Mathematical Society, 56(6):2014–2023, 2024

    work page 2014

  6. [6]

    P. Erd˝ os. Graph theory and probability.Canadian Journal of Mathematics, 11:34–38, 1959

    work page 1959

  7. [7]

    Hefty, P

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

    work page arXiv 2025

  8. [8]

    Keevash, E

    P. Keevash, E. Long, and J. Skokan. Cycle-complete Ramsey numbers.Int. Math. Res. Not. IMRN, pages 277–302, 2021

    work page 2021

  9. [9]

    Li and W

    Y. Li and W. Zang. The independence number of graphs with a forbidden cycle and Ramsey numbers. J. Comb. Optim., 7(4):353–359, 2003

    work page 2003

  10. [10]

    Mattheus and J

    S. Mattheus and J. Verstra¨ ete. The asymptotics ofr(4, t).Annals of Mathematics, 199(2):919–941, 2024

    work page 2024

  11. [11]

    Mubayi and J

    D. Mubayi and J. Verstra¨ ete. A note on pseudorandom Ramsey graphs.Journal of the European Math- ematical Society (EMS Publishing), 26(1), 2024

    work page 2024

  12. [12]

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

    work page 1983

  13. [13]

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

    work page 1977

  14. [14]

    B. Sudakov. A note on odd cycle-complete graph Ramsey numbers.Electron. J. Combin., 9(1):Note 1, 4, 2002

    work page 2002

  15. [15]

    V. H. Vu. Spectral norm of random matrices. InProceedings of the thirty-seventh annual ACM sympo- sium on Theory of computing, pages 423–430, 2005. Instituto de Matem´atica Pura e Aplicada (IMPA). Email address:marcelo.campos@impa.br King’s College London, Department of Mathematics. Email address:matthew.jenssen@kcl.ac.uk Northwestern University. Departme...

    work page 2005