On the structural growth of bipartite Ramsey numbers

Meng Ji

arxiv: 2604.20668 · v3 · submitted 2026-04-22 · 🧮 math.CO

On the structural growth of bipartite Ramsey numbers

Meng Ji This is my paper

Pith reviewed 2026-05-10 00:08 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C55

keywords bipartite ramsey numbersasymptotic boundseven cycleszarankiewicz numbersstructural parametersmulticolor ramsey numberslinear upper bounds

0 comments

The pith

For a fixed bipartite graph G with p vertices and q edges, the bipartite Ramsey number br(G, K_{n,n}) grows at least like C times (n over log n) to the power (q-1) over (p-2).

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

The paper seeks to tie the asymptotic size of bipartite Ramsey numbers to concrete structural features of a fixed graph, rather than treating all graphs the same. It proves a lower bound showing that the exponent in the growth rate is determined by the ratio of edges to vertices in G, which implies that graphs with higher edge density force larger host graphs before a monochromatic copy is guaranteed. This distinction matters because it separates graphs that produce only linear Ramsey numbers from those that require superlinear size. The work also supplies matching-style upper bounds for even cycles in both multicolor and mixed settings, obtained by combining known Zarankiewicz estimates with a counting argument over potential monochromatic copies.

Core claim

For any fixed bipartite graph G with p vertices and q edges we have br(G, K_{n,n}) > C (n / log n)^{(q-1)/(p-2)}. In addition, the multicolor number satisfies br_k(C_{2t}; K_{n,n}) ≤ c_{t,k} n² / log² n, and for any connected bipartite graph G with m edges the mixed number obeys br(C_{2t}, G) ≤ m/2 + 29t √m / 2.

What carries the argument

The bipartite Ramsey number br(H1, H2) together with Zarankiewicz extremal functions that control the maximum edges without a complete bipartite subgraph, combined with double-counting on the incidences of even cycles in a colored host graph.

If this is right

Sufficiently dense fixed bipartite graphs G cannot be bipartite-Ramsey-size-linear.
The multicolor bipartite Ramsey number for any even cycle is at most quadratic in n divided by the square of the logarithm.
When one side is an even cycle, the Ramsey number with any connected bipartite graph G is bounded by a linear function of the number of edges in G plus a square-root correction term.

Where Pith is reading between the lines

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

The exponent (q-1)/(p-2) may serve as a simple proxy for the degeneracy or average degree of G and could be compared with other density measures in extremal graph theory.
The double-counting technique used for cycles might extend to other sparse bipartite graphs whose copies can be counted via incidence relations.
The nearly linear upper bound for br(C_{2t}, G) hints that forbidding a cycle on one side can sometimes reduce the Ramsey number to essentially the size of the second graph.

Load-bearing premise

The lower-bound exponent and the cycle upper bounds rest on the existence of unspecified positive constants coming from prior Zarankiewicz estimates, without fresh derivation of their error terms or exhaustive verification of the double-counting cases.

What would settle it

An explicit two-edge-coloring of K_{M,M} with M smaller than C (n / log n)^{(q-1)/(p-2)} that contains neither a monochromatic copy of the fixed G nor a monochromatic K_{n,n} would falsify the claimed lower bound for large n.

read the original abstract

Bipartite Ramsey numbers is the smallest size of a complete bipartite graph $K_{N,N}$ such that every edge-coloring with a given number of colors inevitably yields a monochromatic copy of a prescribed bipartite graph. While exact values have been determined for certain specific graphs, the general asymptotic behavior of these numbers in terms of structural graph parameters remains poorly understood. In this paper, we investigate structure-dependent growth phenomena in bipartite Ramsey theory. For a fixed bipartite graph $G$ with $p$ vertices and $q$ edges, we first establish a lower bound of the form $\operatorname{br}(G,K_{n,n}) > C \bigl(\frac{n}{\log n}\bigr)^{(q-1)/(p-2)}$. As a corollary, we show that sufficiently dense bipartite graphs fail to be bipartite Ramsey size linear. Turning to even cycles and complete bipartite graphs, we obtain an upper bound on the multicolor bipartite Ramsey number $\operatorname{br}_k(C_{2t};K_{n,n}) \le c_{t,k}\, n^2/\log^2 n$, which follows from classical estimates for Zarankiewicz numbers together with a double-counting argument. Building on this result, we further derive a refined linear upper bound of the form $\operatorname{br}(C_{2t},G) \le \frac{m}{2} + \frac{29t\sqrt{m}}{2}$, valid for any connected bipartite graph $G$ with $m$ edges and no isolated vertices.

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 gives a structure-dependent lower bound for br(G, K_{n,n}) with exponent (q-1)/(p-2) and some refined upper bounds for even-cycle cases, but the double-counting step for the log-squared term is asserted rather than shown in detail.

read the letter

This paper sharpens a few asymptotic statements inside bipartite Ramsey theory. The main new pieces are the lower bound br(G, K_{n,n}) > C (n / log n)^{(q-1)/(p-2)} for a fixed bipartite G with p vertices and q edges, the multicolor upper bound br_k(C_{2t}; K_{n,n}) ≤ c_{t,k} n² / log² n derived from Zarankiewicz plus counting, and the linear upper bound br(C_{2t}, G) ≤ m/2 + 29t √m / 2 for connected G with m edges. These forms are not direct reductions of earlier cited results, so they count as incremental additions to the literature on structure-dependent growth rates. The lower bound also yields the corollary that dense enough G cannot be linear in the Ramsey sense, which is a clean structural observation. The upper bounds reuse classical Zarankiewicz estimates in a straightforward way and produce explicit constants in the linear case, which is useful for specialists who want concrete expressions rather than big-O statements. The soft spot is the double-counting argument that produces the log² n factor in the multicolor cycle bound. The abstract says it follows from classical estimates plus counting, yet gives no steps for how degrees or paths are tallied, nor does it check boundary cases such as small t, low-degree vertices, or color interactions. Without those steps visible, it is hard to confirm the precise power of the log or that the constant c_{t,k} stays positive for all parameters. The free constants C and c_{t,k} are standard in this area but make the results more qualitative than sharp. This is work for people already inside extremal graph theory and bipartite Ramsey numbers. A reader who follows the Zarankiewicz literature or wants explicit refinements for cycles will find the parameterized forms and the dense-graph corollary worth noting. It does not resolve any long-standing open problems and stays within known methods, so it is not essential reading outside the subfield. The claims look coherent on their own terms and engage the literature honestly, even if the counting details need verification. I would send it to a serious referee rather than desk-reject it; the new exponent and the refined linear bound are worth checking in full, with the expectation that the double-counting argument gets written out explicitly.

Referee Report

2 major / 2 minor

Summary. The manuscript investigates asymptotic growth of bipartite Ramsey numbers br(G, H). For a fixed bipartite graph G with p vertices and q edges, it establishes the lower bound br(G, K_{n,n}) > C (n / log n)^{(q-1)/(p-2)}. It derives the multicolor upper bound br_k(C_{2t}; K_{n,n}) ≤ c_{t,k} n² / log² n from classical Zarankiewicz estimates combined with a double-counting argument. As a further consequence it obtains the linear upper bound br(C_{2t}, G) ≤ m/2 + 29t √m / 2 for any connected bipartite G with m edges and no isolated vertices.

Significance. If the stated bounds are valid, the work supplies concrete structural dependence of bipartite Ramsey numbers on the edge density and connectivity parameters of G, including the observation that sufficiently dense G cannot be bipartite-Ramsey linear. The explicit coefficient 29t in the linear upper bound and the use of off-the-shelf Zarankiewicz results to obtain the log² n factor constitute reusable quantitative improvements.

major comments (2)

[Proof of Theorem on br_k(C_{2t}; K_{n,n})] The derivation of the upper bound br_k(C_{2t}; K_{n,n}) ≤ c_{t,k} n² / log² n (stated in the abstract and presumably proved in the section following the lower-bound result) asserts that the log² n factor follows from classical Zarankiewicz estimates plus a double-counting argument, yet supplies neither the explicit counting steps (how vertex degrees, path lengths of length t-1, or monochromatic color interactions are tallied) nor verification that the resulting constant c_{t,k} remains positive for all t ≥ 2 and k ≥ 1. Because this counting produces the claimed exponent, the gap directly affects the central upper-bound claim.
[Abstract and the paragraph deriving the cycle upper bound] The abstract claims that the upper bounds follow from classical Zarankiewicz estimates “together with a double-counting argument,” but the manuscript contains no re-derivation or error-term analysis of the invoked Zarankiewicz bounds that would confirm the constants stay positive and the claimed form is preserved for all t and k. This omission is load-bearing for the asserted growth rate.

minor comments (2)

[Introduction] The notation br_k is introduced without an explicit definition in the opening paragraphs; a one-sentence clarification of the number of colors would improve readability.
[Derivation of the bound for br(C_{2t}, G)] The constant 29t appearing in the linear upper bound is stated without an accompanying sentence tracing its origin (e.g., which inequality in the preceding double-counting step produces the factor 29).

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on the clarity of our upper-bound arguments. We address the major comments point by point below and will revise the manuscript accordingly.

read point-by-point responses

Referee: [Proof of Theorem on br_k(C_{2t}; K_{n,n})] The derivation of the upper bound br_k(C_{2t}; K_{n,n}) ≤ c_{t,k} n² / log² n (stated in the abstract and presumably proved in the section following the lower-bound result) asserts that the log² n factor follows from classical Zarankiewicz estimates plus a double-counting argument, yet supplies neither the explicit counting steps (how vertex degrees, path lengths of length t-1, or monochromatic color interactions are tallied) nor verification that the resulting constant c_{t,k} remains positive for all t ≥ 2 and k ≥ 1. Because this counting produces the claimed exponent, the gap directly affects the central upper-bound claim.

Authors: We agree that the current write-up of the upper bound br_k(C_{2t}; K_{n,n}) ≤ c_{t,k} n² / log² n presents the double-counting argument at a high level without spelling out every intermediate tally. In the revised version we will expand this section with explicit counting steps: we will detail how the degrees of vertices in each monochromatic copy are bounded via the Zarankiewicz function, how the number of paths of length t-1 is enumerated in the auxiliary graph, and how the k-color interactions are aggregated through a union bound. We will also insert a short calculation verifying that the resulting constant c_{t,k} is strictly positive for every t ≥ 2 and k ≥ 1 by exhibiting explicit positive lower bounds on the relevant Zarankiewicz quantities. These additions will appear immediately after the lower-bound theorem. revision: yes
Referee: [Abstract and the paragraph deriving the cycle upper bound] The abstract claims that the upper bounds follow from classical Zarankiewicz estimates “together with a double-counting argument,” but the manuscript contains no re-derivation or error-term analysis of the invoked Zarankiewicz bounds that would confirm the constants stay positive and the claimed form is preserved for all t and k. This omission is load-bearing for the asserted growth rate.

Authors: The abstract summarizes the method concisely, as is conventional. We nevertheless accept that a brief re-derivation with error terms would improve transparency. In the revision we will add a short paragraph (or a dedicated remark) that recalls the classical Zarankiewicz upper bounds together with their error terms, then shows by direct substitution that the constants remain positive and that the n² / log² n form is preserved uniformly for all t ≥ 2 and k ≥ 1. This paragraph will be placed in the section deriving the cycle upper bound and will also be referenced from the abstract. revision: yes

Circularity Check

0 steps flagged

No circularity: bounds derived from external classical results

full rationale

The paper's lower bound incorporates an unspecified constant C drawn from standard Zarankiewicz-type estimates, while the upper bound br_k(C_{2t};K_{n,n}) is explicitly stated to follow from those same external estimates plus a double-counting argument. The refined linear bound for br(C_{2t},G) is presented as a consequence of the preceding result. No equation reduces any claimed growth rate to a quantity defined by the authors' own fitted data, self-citations, or ansatz smuggled through prior work; the derivations remain dependent on independent external theorems rather than internal self-definition or renaming.

Axiom & Free-Parameter Ledger

2 free parameters · 2 axioms · 0 invented entities

The paper invokes standard combinatorial facts about Zarankiewicz numbers and double counting without introducing new free parameters beyond unspecified positive constants C and c_{t,k}; no new entities are postulated.

free parameters (2)

C
Positive constant whose existence is asserted for the lower bound but whose value is not computed or bounded explicitly.
c_{t,k}
Positive constant depending on t and k whose existence follows from the Zarankiewicz estimates but is not derived in closed form.

axioms (2)

standard math Classical upper bounds on the Zarankiewicz number z(m,n;s,t) hold for the relevant parameters.
Invoked to obtain the cycle upper bound; cited as 'classical estimates' without re-proof.
domain assumption Double counting of edges or paths in the colored complete bipartite graph yields the stated inequality.
Central step for the upper bound on br_k(C_{2t}; K_{n,n}); no explicit counting identity is supplied in the abstract.

pith-pipeline@v0.9.0 · 5563 in / 1548 out tokens · 40097 ms · 2026-05-10T00:08:15.456897+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

Beineke and A.J

L.W. Beineke and A.J. Schwenk, On a bipartite form of the Ramsey problem,Proc. 5th British Combin. Conf.(1975), Congressus Numerantium XV, Utilitas Mathematica, Winnipeg, 1975, pp. 17–22

work page 1975
[2]

Bollob´ as, Extremal graph theory, inHandbook of Combinatorics, Vol

B. Bollob´ as, Extremal graph theory, inHandbook of Combinatorics, Vol. II, R.L. Graham, M. Gr¨ otschel, and L. Lov´ asz, eds., MIT Press, Cambridge, MA, 1995

work page 1995
[3]

Buci´ c, H

M. Buci´ c, H. Letzter and B. Sudakov, 3-color bipartite Ramsey number of cycles and paths, J. Graph Theory92(2019), 445–459

work page 2019
[4]

Buci´ c, H

M. Buci´ c, H. Letzter and B. Sudakov, Multicolour bipartite Ramsey number of paths,Electron. J. Combin.26(2019), P3.60

work page 2019
[5]

Conlon, A new upper bound for the bipartite Ramsey problem,J

D. Conlon, A new upper bound for the bipartite Ramsey problem,J. Graph Theory58(2008), 351–356

work page 2008
[6]

Decamillis and Z.X

G. Decamillis and Z.X. Song, Multicolor bipartite Ramsey number of double stars, arXiv:2312.03670(2023). 10

work page arXiv 2023
[7]

Erd˝ os, R.J

P. Erd˝ os, R.J. Faudree, C.C. Rousseau, and R.H. Schelp, Ramsey size linear graphs,Combin. Probab. Comput.2(1993), 389–399

work page 1993
[8]

Faudree and R.H

R.J. Faudree and R.H. Schelp, Path-path Ramsey-type numbers for the complete bipartite graph,J. Combin. Theory Ser. B19(1975), 161–173

work page 1975
[9]

Gy´ arf´ as and J

A. Gy´ arf´ as and J. Lehel, A Ramsey-type problem in directed and bipartite graphs,Period. Math. Hungar.3(1973), 299–304

work page 1973
[10]

Hattingh and M.A

J.H. Hattingh and M.A. Henning, Bipartite Ramsey theory,Utilitas Math.53(1998), 217–230

work page 1998
[11]

Irving, A bipartite Ramsey problem and Zarankiewicz numbers,Glasgow Math

R.W. Irving, A bipartite Ramsey problem and Zarankiewicz numbers,Glasgow Math. J.19 (1978), 13–26

work page 1978
[12]

Liu and Y

M. Liu and Y. Li, Bipartite Ramsey numbers of cycles for random graphs,Graphs Combin. 37(2021), 2703–2711

work page 2021
[13]

Naor and J

A. Naor and J. Verstra¨ ete, A note on bipartite graphs without 2k-cycles,Combin. Probab. Comput.14(2005), 845–849

work page 2005
[14]

Yan and Y

Z. Yan and Y. Peng, Bipartite Ramsey numbers of cycles,Eur. J. Combin.118(2024), 103921

work page 2024
[15]

Zhang and Y

R. Zhang and Y. Sun, The bipartite Ramsey numbersb(C 2m;K 2,2),Electron. J. Combin.18 (2011), #P51. 11

work page 2011

[1] [1]

Beineke and A.J

L.W. Beineke and A.J. Schwenk, On a bipartite form of the Ramsey problem,Proc. 5th British Combin. Conf.(1975), Congressus Numerantium XV, Utilitas Mathematica, Winnipeg, 1975, pp. 17–22

work page 1975

[2] [2]

Bollob´ as, Extremal graph theory, inHandbook of Combinatorics, Vol

B. Bollob´ as, Extremal graph theory, inHandbook of Combinatorics, Vol. II, R.L. Graham, M. Gr¨ otschel, and L. Lov´ asz, eds., MIT Press, Cambridge, MA, 1995

work page 1995

[3] [3]

Buci´ c, H

M. Buci´ c, H. Letzter and B. Sudakov, 3-color bipartite Ramsey number of cycles and paths, J. Graph Theory92(2019), 445–459

work page 2019

[4] [4]

Buci´ c, H

M. Buci´ c, H. Letzter and B. Sudakov, Multicolour bipartite Ramsey number of paths,Electron. J. Combin.26(2019), P3.60

work page 2019

[5] [5]

Conlon, A new upper bound for the bipartite Ramsey problem,J

D. Conlon, A new upper bound for the bipartite Ramsey problem,J. Graph Theory58(2008), 351–356

work page 2008

[6] [6]

Decamillis and Z.X

G. Decamillis and Z.X. Song, Multicolor bipartite Ramsey number of double stars, arXiv:2312.03670(2023). 10

work page arXiv 2023

[7] [7]

Erd˝ os, R.J

P. Erd˝ os, R.J. Faudree, C.C. Rousseau, and R.H. Schelp, Ramsey size linear graphs,Combin. Probab. Comput.2(1993), 389–399

work page 1993

[8] [8]

Faudree and R.H

R.J. Faudree and R.H. Schelp, Path-path Ramsey-type numbers for the complete bipartite graph,J. Combin. Theory Ser. B19(1975), 161–173

work page 1975

[9] [9]

Gy´ arf´ as and J

A. Gy´ arf´ as and J. Lehel, A Ramsey-type problem in directed and bipartite graphs,Period. Math. Hungar.3(1973), 299–304

work page 1973

[10] [10]

Hattingh and M.A

J.H. Hattingh and M.A. Henning, Bipartite Ramsey theory,Utilitas Math.53(1998), 217–230

work page 1998

[11] [11]

Irving, A bipartite Ramsey problem and Zarankiewicz numbers,Glasgow Math

R.W. Irving, A bipartite Ramsey problem and Zarankiewicz numbers,Glasgow Math. J.19 (1978), 13–26

work page 1978

[12] [12]

Liu and Y

M. Liu and Y. Li, Bipartite Ramsey numbers of cycles for random graphs,Graphs Combin. 37(2021), 2703–2711

work page 2021

[13] [13]

Naor and J

A. Naor and J. Verstra¨ ete, A note on bipartite graphs without 2k-cycles,Combin. Probab. Comput.14(2005), 845–849

work page 2005

[14] [14]

Yan and Y

Z. Yan and Y. Peng, Bipartite Ramsey numbers of cycles,Eur. J. Combin.118(2024), 103921

work page 2024

[15] [15]

Zhang and Y

R. Zhang and Y. Sun, The bipartite Ramsey numbersb(C 2m;K 2,2),Electron. J. Combin.18 (2011), #P51. 11

work page 2011