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

Abisek Dewan; Rajiv Mishra; Sayan Gupta

arxiv: 2604.02086 · v3 · submitted 2026-04-02 · 🧮 math.CO

On Ramsey number of K_(2,n) versus even cycles

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

Pith reviewed 2026-05-13 20:50 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C55

keywords Ramsey numbersgraph theoryeven cyclesstars and double starsK_{2,n}extremal graph theorycycle embeddings

0 comments

The pith

The Ramsey number R(K_{2,n}, C_m) equals R(K_{1,n}, C_m) for even m between n and 2n-4008 when n is at least 4516.

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 smallest number forcing a copy of K_{2,n} or a complementary even cycle C_m is the same as the number forcing a star K_{1,n} or the same cycle, for n at least 4516 and m even in that interval. This equality is obtained by showing that the critical colorings and graph structures that avoid one pair also avoid the other through detailed case analysis on vertex degrees and cycle embeddings. A reader would care because the star-cycle Ramsey numbers are already determined in many cases, so the result immediately supplies exact values for the harder K_{2,n} versions without separate computation. It also suggests that increasing the number of edges in the forbidden subgraph from one to two does not raise the Ramsey threshold inside the stated range.

Core claim

The authors prove that R(K_{2,n}, C_m) equals R(K_{1,n}, C_m) for every even m lying in the closed interval from n to 2n-4008, whenever n is at least 4516. The proof proceeds by structural arguments that equate the extremal properties of graphs avoiding K_{2,n} with those avoiding K_{1,n} relative to the absence of even cycles in the complement.

What carries the argument

The equality R(K_{1,n}, C_m) = R(K_{2,n}, C_m) obtained via case analysis on the structure of Ramsey-critical graphs and embeddings of even cycles.

If this is right

Exact values for R(K_{2,n}, C_m) are now known throughout the given range because they coincide with the already-determined star values.
The equality is restricted to even m and to a linear window of length roughly n.
The result raises the explicit open question whether R(K_{1,n}, C_m) equals R(K_{t,n}, C_m) for any fixed t greater than 2 when n is large enough.
The same structural techniques may apply when the forbidden subgraph is any fixed bipartite graph with maximum degree two.

Where Pith is reading between the lines

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

For sufficiently large n the equality may hold for all even m above n, not merely up to 2n minus a constant.
The stabilization suggests that Ramsey numbers of bounded-degree bipartite graphs versus even cycles become insensitive to the precise degree once n exceeds a threshold.
Computational checks for n just below 4516 could locate the exact point where the equality begins to hold.

Load-bearing premise

The structural arguments equating the two Ramsey numbers require n to be at least 4516 and m even within the interval [n, 2n-4008].

What would settle it

A graph on R(K_{1,n}, C_m) minus one vertices that contains no K_{2,n} subgraph whose complement nevertheless contains no C_m would show the numbers are unequal.

Figures

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

**Figure 1.** Figure 1: Existence of Cm in G when G[X′ ] is disconnected |{NG(b1) ∪ NG(b2)} ∩ {(Y \ Y ′ ) \ {y}}| ≥ 1000 − k. (5) Set Z = {NG(b1) ∪ NG(b2)} ∩ {(Y \ Y ′ ) \ {y}}. Now we claim that there exists y ′ ∈ Z such that y ′ ∼ a ′ for some a ′ ∈ A \ {a}. If not, then for all a ′ ∈ A \ {a}, a ′ ≁ y ′ for all y ′ ∈ Z. In this case, there exist a1, a2 ∈ A \ {a} such that |NG(a1) ∩ NG(a2)| ≥ |B| + |Z| + |{v}| ≥ n, a contradicti… view at source ↗

**Figure 2.** Figure 2: Existence of Cm in G when κ(G[X′ ]) = 1 Case 3. Assume that κ(G[X′ ]) = 2, that is, there exist two vertices w, w′ ∈ X′ such that they form a cut set for G[X′ ]. Assume X′ \ {w, w′} = A ⊔ B, where n − 2002 ≤ |A| ≤ n − 1002 n − 1002 ≤ |B| ≤ n − 2, Similar to the previous cases, we consider |A| = n − 1002 − k, |B| = n − 1002 + k, for some 0 ≤ k ≤ 1000. Again, similar to the previous cases, we have that G[A] … view at source ↗

**Figure 3.** Figure 3: ). We choose such b and b ′ so that their cyclic distance on a Hamiltonian cycle in G[B] is minimum. Let P1 and P2 denote the two b−b ′ subpaths on that cycle, where P1 is the shorter path and P2 is the longer one. Sub-case 3(I). Suppose 4 ≤ |V (P1)| ≤ 2008. Let P3 = wP2w ′ . Then the order of P3 satisfies n − 3006 + k ≤ |V (P3)| ≤ n − 1002 + k, and hence we may parametrize it as |V (P3)| = n − 3006 + k + … view at source ↗

read the original abstract

For graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the smallest integer $N$ such that every graph $\Gamma$ on $N$ vertices contains $G$ or its complement $\overline{\Gamma}$ contains $H$ as a subgraph. In graph Ramsey theory, the star-cycle Ramsey number is well-studied throughout the years. Whereas the Ramsey number of $K_{2,n}$ versus cycle is challenging to determine due to increased structural complexity. In this article, we have obtained an exact value of the Ramsey number $R(K_{2,n}, C_{m})$ for even $m\in [n, 2n-4008]$ and $n\geq 4516$. In particular, we show that $$R(K_{1,n}, C_{m})= R(K_{2,n}, C_{m})$$ for all even $m\in [n, 2n-4008]$ and $n\geq 4516$. This leads to an interesting question: For fixed $t$, does there exist $n_0(t)\in \mathbb{N}$ such that $R(K_{1,n}, C_m)=R(K_{t,n}, C_m)$ for all $n \geq n_0(t)$ and for a given range of even $m$?

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 proves R(K_{2,n}, C_m) equals the star version for even m in [n, 2n-4008] when n is at least 4516, extending known star-cycle results but only inside a narrow window.

read the letter

The core contribution is showing that the Ramsey number R(K_{2,n}, C_m) matches R(K_{1,n}, C_m) exactly for even m from n up to 2n minus 4008, once n reaches 4516. This upgrades the forbidden subgraph from a star to a double star while keeping the cycle-forcing behavior in the complement. The argument appears to reuse the upper bound already known for the star and then adds a counting or embedding step to rule out the extra edges that would create K_{2,n}. That step is where the large thresholds come in, giving enough room for the inequalities to close. The paper does this cleanly enough that the equality holds inside the stated range, and the question it poses about generalizing to K_{t,n} is a natural next direction. The main limitation is the size of the constants: 4516 and 4008 are chosen so the error terms fit, which means the result does not yet reach smaller n or m closer to 2n. No small-case verification or computer checks are mentioned, so it is unclear how much slack is actually needed. The proof strategy itself looks standard for this area and does not introduce circular steps. This work is aimed at people who track exact Ramsey numbers for bipartite graphs versus even cycles. A reader already familiar with the star case will see the incremental advance right away. It is worth sending to referees because the claim is concrete, the range is explicit, and the structural upgrade is the kind of thing the community checks carefully. Revisions would likely focus on tightening the constants or explaining why they cannot be lowered much further.

Referee Report

1 major / 0 minor

Summary. The manuscript establishes that R(K_{2,n}, C_m) equals R(K_{1,n}, C_m) for every even m in the interval [n, 2n-4008] whenever n ≥ 4516. The argument proceeds by taking a graph Γ on R(K_{1,n}, C_m) vertices with no K_{2,n} subgraph and showing that its complement must contain C_m, upgrading the known star-cycle result via degree and embedding arguments that close only inside the stated parameter range.

Significance. If the equality holds, the paper supplies exact values for a family of K_{2,n}-cycle Ramsey numbers over a substantial interval of even m, extending the star case and indicating that the Ramsey number stabilizes already at t=2 for large n. The closing question about generalization to fixed t is a natural direction suggested by the result.

major comments (1)

The thresholds n ≥ 4516 and m ≤ 2n-4008 are introduced precisely to absorb the error terms that arise when upgrading a maximum-degree-<n assumption to the absence of K_{2,n} while still guaranteeing an even cycle embedding in the complement. The manuscript does not display the explicit inequality chain or the numerical derivation that produces these two constants from the preceding counting lemmas, so it is impossible to verify whether the bounds are forced by the estimates or could be improved.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and insightful comments on our manuscript. We are pleased that the referee recognizes the significance of establishing the equality R(K_{2,n}, C_m) = R(K_{1,n}, C_m) for the specified range. We address the major comment below and will revise the manuscript to incorporate the necessary clarifications.

read point-by-point responses

Referee: The thresholds n ≥ 4516 and m ≤ 2n-4008 are introduced precisely to absorb the error terms that arise when upgrading a maximum-degree-<n assumption to the absence of K_{2,n} while still guaranteeing an even cycle embedding in the complement. The manuscript does not display the explicit inequality chain or the numerical derivation that produces these two constants from the preceding counting lemmas, so it is impossible to verify whether the bounds are forced by the estimates or could be improved.

Authors: We agree that the explicit derivation of these thresholds is missing from the manuscript and should be included for transparency and verifiability. The constants are chosen to ensure that all error terms from the degree bounds and the cycle embedding lemmas are dominated by the main terms for n sufficiently large. In the revised version, we will insert a detailed calculation section immediately following the statement of the main lemmas, showing the full chain of inequalities that lead to n ≥ 4516 and m ≤ 2n - 4008. This addition will also allow readers to assess potential improvements to the bounds with refined estimates. revision: yes

Circularity Check

0 steps flagged

No circularity; equality follows from independent structural arguments on known star Ramsey bounds

full rationale

The paper establishes R(K_{2,n},C_m)=R(K_{1,n},C_m) for the stated range by proving that any graph on R(K_{1,n},C_m) vertices without a K_{2,n} subgraph must still contain C_m in the complement. This upgrade from the known K_{1,n} upper bound proceeds via degree-bounded counting and embedding lemmas whose error terms are absorbed precisely when n≥4516 and m≤2n-4008. These thresholds are explicit parameters in the inequalities rather than fitted outputs; the argument cites prior external results on star-cycle Ramsey numbers and does not reduce any central claim to a self-citation chain, self-definition, or renamed fit. The derivation is therefore self-contained against the external benchmark of the star case.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard combinatorial axioms without introducing new free parameters or entities.

axioms (1)

standard math Basic properties of graphs, subgraphs, and Ramsey numbers as defined in standard graph theory literature.
The paper uses these to define and prove the equality.

pith-pipeline@v0.9.0 · 5539 in / 1256 out tokens · 55453 ms · 2026-05-13T20:50:33.860093+00:00 · methodology

discussion (0)

Forward citations

Cited by 2 Pith papers

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

On Ramsey goodness of $K_{2,n}$ versus cycles
math.CO 2026-05 unverdicted novelty 7.0

R(K_{2,n}, C_m) = m+1 for m ≥ 3n+4, proving C_m is K_{2,n}-good, with a counterexample construction showing it fails for even m when n ≥ m+2.
On Ramsey goodness of $K_{2,n}$ versus cycles
math.CO 2026-05 unverdicted novelty 6.0

R(K_{2,n}, C_m) equals m+1 for m at least 3n+4, proving C_m is K_{2,n}-good in this range, with a disproof for even m when n is at least m+2.

Reference graph

Works this paper leans on

1 extracted references · 1 canonical work pages · cited by 1 Pith paper

[1]

Allen, T

[1]P. Allen, T. Luczak, J. Polcyn, and Y. Zhang,The ramsey number of a long even cycle versus a star, Journal of Combinatorial Theory, Series B, 162 (2023), pp. 144–153. 2 [2]J. A. Bondy,Pancyclic graphsI, J. Combin. Theory Ser. B, 11 (1971), pp. 80–84. 4 [3]S. Brandt, R. Faudree, and W. Goddard,Weakly pancyclic graphs, Journal of Graph Theory, 27 (1998),...

work page arXiv 2023

[1] [1]

Allen, T

[1]P. Allen, T. Luczak, J. Polcyn, and Y. Zhang,The ramsey number of a long even cycle versus a star, Journal of Combinatorial Theory, Series B, 162 (2023), pp. 144–153. 2 [2]J. A. Bondy,Pancyclic graphsI, J. Combin. Theory Ser. B, 11 (1971), pp. 80–84. 4 [3]S. Brandt, R. Faudree, and W. Goddard,Weakly pancyclic graphs, Journal of Graph Theory, 27 (1998),...

work page arXiv 2023