pith. sign in

arxiv: 2605.06253 · v2 · submitted 2026-05-07 · 🧮 math.CO

On Ramsey goodness of K_(2,n) versus cycles

Abisek Dewan , Sayan Gupta , Rajiv Mishra This is my paper

Pith reviewed 2026-05-11 02:12 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C55
keywords ramsey numbersramsey goodnesscyclescomplete bipartite graphsK_{2,n}C_m
0
0 comments X

The pith

R(K_{2,n}, C_m) equals m+1 for all m at least 3n+4, so the cycle is K_{2,n}-good in this range.

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

The paper determines exact Ramsey numbers for the pair consisting of the complete bipartite graph K_{2,n} and a cycle of length m. It proves that R(K_{2,n}, C_{{m,m+1}}) equals m+1 whenever m is at least 2n+1, and deduces the ordinary Ramsey number R(K_{2,n}, C_m) equals m+1 for m at least 3n+4. This equality establishes the goodness of the cycle with respect to K_{2,n} in the stated range and improves an earlier result of Pokrovskiy and Sudakov. The authors also supply an explicit construction showing that goodness fails when the cycle is even and n is at least m+2.

Core claim

We prove that R(K_{2,n}, C_{{m,m+1}})=m+1 for all m≥2n+1, and consequently establish that R(K_{2,n},C_m)=m+1 for all m≥3n+4. This proves that C_m is K_{2,n}-good in this range.

What carries the argument

The definition of H-goodness: R(G,H) equals (|G|-1)(χ(H)-1) + σ(H), where σ(H) is the size of the smallest color class in a proper χ(H)-coloring of H.

If this is right

  • C_m is K_{2,n}-good for every m ≥ 3n+4.
  • The result improves a special case of the Pokrovskiy–Sudakov theorem on Ramsey goodness.
  • Goodness fails for every even m when n ≥ m+2, via an explicit counterexample graph.
  • The threshold separating good and non-good regimes depends on both the parity of m and the relative size of n.

Where Pith is reading between the lines

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

  • The same proof technique may extend the goodness range for other bipartite graphs against cycles.
  • The counterexample construction for even cycles suggests that parity plays a structural role in whether the expected Ramsey bound is attained.
  • Determining the precise threshold between the good and non-good regimes for fixed n remains open.

Load-bearing premise

The cycle length m satisfies m ≥ 2n+1 (or m ≥ 3n+4 for the single-cycle case) and the usual two-color Ramsey definition applies without further restrictions on the host graph.

What would settle it

A red-blue coloring of the edges of the complete graph on m vertices that contains neither a red K_{2,n} nor a blue cycle of length m (or of lengths m and m+1) would falsify the claimed equality.

Figures

Figures reproduced from arXiv: 2605.06253 by Abisek Dewan, Rajiv Mishra, Sayan Gupta.

Figure 1
Figure 1. Figure 1: Distribution of neighbors of x and y on C So we let s − t = 1. If A = {s, s + 2, . . . , m − 1}, then we proceed similarly to obtain a contradiction. Otherwise let A = {s, s + 2, . . . , s + 2i} ∪ {s + 2i + 3, s + 2i + 5, . . . , m − 1} for some fixed i ≥ 0. No other case of A is possible here (see view at source ↗
Figure 2
Figure 2. Figure 2: Representation of stretches containing the vertices of view at source ↗
Figure 3
Figure 3. Figure 3: Graph G on 3m + t + 1 vertices, G ⊉ K2,2m+t and G ⊉ C2m, 3 ≤ t < m + 1. Lemma 17. K2,n is not C2m-good, that is, R(K2,n, C2m) > n + m + 1, for any integer n ∈ S∞ q=2{q(m + 1) − 2, q(m + 1) − 1, q(m + 1)}. Proof. For q ≥ 2 and t ∈ {0, 1, 2}, take n = q(m + 1) − t and consider the graph G on n + m + 1 vertices such that G = K1 ∨ ( K2m−t−2 ∪ Km+4 ∪ q [−2 i=1 Km+1!) . 14 view at source ↗
read the original abstract

A graph $G$ is called $H$-good if $R(G,H)=(|G|-1)(\chi(H)-1)+\sigma(H)$, where $\sigma(H)$ denotes the size of the smallest color class in a $\chi(H)$-coloring of $H$. In Ramsey theory, it is an interesting problem to study whether a graph $G$ is $H$-good or not. In this article, we study the Ramsey goodness of the pair $(K_{2,n},C_m)$, which naturally lies between the classical star-cycle and book-cycle problems. We prove that \begin{equation*} R(K_{2,n},C_{\{m,m+1\}})=m+1. \end{equation*} for all $m\ge 2n+1$, and consequently establish that \begin{equation*} R(K_{2,n},C_{m})=m+1. \end{equation*} for all $m\ge 3n+4$. This proves that $C_m$ is $K_{2,n}$-good in this range and improves a particular case of a result on the Ramsey goodness by Pokrovskiy and Sudakov. Further, we provide a construction of a graph that disproves the $C_{m}$-goodness of $K_{2,n}$ for all even $m$ satisfying $n\geq m+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 / 3 minor

Summary. The paper proves that the Ramsey number R(K_{2,n}, C_{{m,m+1}}) equals m+1 for all integers m ≥ 2n+1. As a consequence, it shows R(K_{2,n}, C_m) = m+1 for all m ≥ 3n+4, establishing that C_m is K_{2,n}-good in this range. It also supplies an explicit construction disproving K_{2,n}-goodness of C_m for even m whenever n ≥ m+2.

Significance. If the stated bounds hold, the result supplies explicit thresholds at which consecutive cycles (and then single cycles) become K_{2,n}-good, improving a special case of the Pokrovskiy–Sudakov theorem on Ramsey goodness. The matching upper and lower bounds, obtained via codegree arguments for K_{2,n}-freeness together with cycle-embedding lemmas in the complement, and the independent disproof construction for even lengths, add concrete data points to the classification of Ramsey-good pairs involving stars and cycles.

minor comments (3)
  1. The notation C_{{m,m+1}} is introduced without an explicit definition in the abstract or early sections; a sentence clarifying that it denotes the set {C_m, C_{m+1}} would prevent any ambiguity for readers.
  2. The proof of the upper bound for R(K_{2,n}, C_{{m,m+1}}) relies on an embedding lemma for long cycles; the manuscript should state the precise codegree threshold used and verify that m ≥ 2n+1 is sufficient to satisfy all hypotheses of that lemma.
  3. In the disproof construction for even m with n ≥ m+2, the extremal graph on m vertices is described only briefly; adding a short diagram or explicit edge-set description would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary and recommendation of minor revision. No specific major comments were raised in the report, so we have no points to address point-by-point at this stage. We remain ready to incorporate any minor editorial suggestions that may be provided.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes the stated Ramsey equalities via explicit upper-bound arguments (any K_{2,n}-free graph on m+1 vertices contains a C_m or C_{m+1} in the complement, using codegree bounds and embedding lemmas) and matching lower-bound constructions on m vertices. These steps rely on standard extremal graph theory techniques and the given range conditions m ≥ 2n+1 (or 3n+4), without any parameter fitting, self-referential definitions of the Ramsey number, or load-bearing self-citations that reduce the central claim to its own inputs. The disproof construction for even m is likewise an independent explicit graph and does not interact with the positive results.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard definitions of Ramsey numbers, chromatic number, and graph goodness from prior literature, with no free parameters fitted to data and no new entities postulated.

axioms (2)
  • standard math Standard definition of the Ramsey number R(G,H) as the smallest number such that any 2-edge-coloring of the complete graph on that many vertices contains a monochromatic G or H.
    Invoked in the statement of the main theorems.
  • standard math Definition of H-goodness: R(G,H) equals (|G|-1)(χ(H)-1) + σ(H).
    Used to interpret the results as proving goodness.

pith-pipeline@v0.9.0 · 5546 in / 1428 out tokens · 38000 ms · 2026-05-11T02:12:33.382923+00:00 · methodology

Review history (2 revisions) →

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

22 extracted references · 22 canonical work pages · 1 internal anchor

  1. [1]

    Journal of the London Mathematical Society , volume=

    Ramsey numbers involving graphs with long suspended paths , author=. Journal of the London Mathematical Society , volume=. 1981 , publisher=

    work page 1981

  2. [2]

    European Journal of Combinatorics , volume=

    Ramsey numbers of long cycles versus books or wheels , author=. European Journal of Combinatorics , volume=. 2010 , publisher=

    work page 2010

  3. [3]

    On Ramsey number of $K_{2,n}$ versus even cycles

    On Ramsey number of K\_ \ 2, n \ versus even cycles , author=. arXiv preprint arXiv:2604.02086 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  4. [4]

    Studies in pure mathematics (presented to Richard Rado) , pages=

    Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency , author=. Studies in pure mathematics (presented to Richard Rado) , pages=. 1971 , organization=

    work page 1971

  5. [5]

    Generalizations of a Ramsey-theoretic result of Chv

    Burr, Stefan A and Erd. Generalizations of a Ramsey-theoretic result of Chv. Journal of Graph Theory , volume=. 1983 , publisher=

    work page 1983

  6. [6]

    Selected topics in graph theory , pages=

    Ramsey graph theory , author=. Selected topics in graph theory , pages=. 1978 , publisher=

    work page 1978

  7. [7]

    Notices of the American Mathematical Society , year=

    Cycle-star Ramsey numbers , author=. Notices of the American Mathematical Society , year=

    work page

  8. [8]

    Journal of combinatorics (Somerville) , volume=

    Narrowing down the gap on cycle-star Ramsey numbers , author=. Journal of combinatorics (Somerville) , volume=. 2016 , publisher=

    work page 2016

  9. [9]

    Journal of Combinatorial Theory, Series B , volume=

    The Ramsey number of a long even cycle versus a star , author=. Journal of Combinatorial Theory, Series B , volume=. 2023 , publisher=

    work page 2023

  10. [10]

    Combinatorica , volume=

    Ramsey-goodness—and otherwise , author=. Combinatorica , volume=. 2013 , publisher=

    work page 2013

  11. [11]

    SIAM Journal on Discrete Mathematics , volume=

    Large book-cycle Ramsey numbers , author=. SIAM Journal on Discrete Mathematics , volume=. 2021 , publisher=

    work page 2021

  12. [12]

    SIAM Journal on Discrete Mathematics , volume=

    Ramsey numbers of books versus long cycles , author=. SIAM Journal on Discrete Mathematics , volume=. 2025 , publisher=

    work page 2025

  13. [13]

    Allen, T

    A study of two Ramsey numbers involving odd cycles , author=. arXiv preprint arXiv:2504.15693 , year=

    work page arXiv

  14. [14]

    Journal of Combinatorial Theory, Series B , volume=

    Cycles in bipartite graphs , author=. Journal of Combinatorial Theory, Series B , volume=. 1981 , publisher=

    work page 1981

  15. [15]

    Proceedings of the London Mathematical Society , volume=

    Some theorems on abstract graphs , author=. Proceedings of the London Mathematical Society , volume=. 1952 , publisher=

    work page 1952

  16. [16]

    SIAM Journal on Discrete Mathematics , volume=

    Ramsey goodness of cycles , author=. SIAM Journal on Discrete Mathematics , volume=. 2020 , publisher=

    work page 2020

  17. [17]

    Advances in Combinatorics , volume=

    Ramsey goodness of books revisited , author=. Advances in Combinatorics , volume=

    work page

  18. [18]

    Journal of Combinatorial Theory, Series B , volume=

    Ramsey goodness of paths , author=. Journal of Combinatorial Theory, Series B , volume=. 2017 , publisher=

    work page 2017

  19. [19]

    Combinatorica , volume=

    Ramsey goodness and beyond , author=. Combinatorica , volume=. 2009 , publisher=

    work page 2009

  20. [20]

    Ars Combinatoria , volume=

    Cycle-book Ramsey numbers , author=. Ars Combinatoria , volume=. 1991 , publisher=

    work page 1991

  21. [21]

    Journal of Graph Theory , volume=

    Weakly pancyclic graphs , author=. Journal of Graph Theory , volume=. 1998 , publisher=

    work page 1998

  22. [22]

    Forum of Mathematics, Sigma , volume=

    Ramsey numbers of cycles versus general graphs , author=. Forum of Mathematics, Sigma , volume=. 2023 , organization=

    work page 2023