PreprintCC BY 4.0arXiv
Another proof that the two color bipartite Ramsey number is O(2t)
Abstract
For positive integers t and q let bq(t) be the smallest integer n so that any coloring of the edges of the complete bipartite graph Kn,n with q colors yields a monochromatic copy of Kt,t. We give an independent proof that b2(t)≤ 128· 2t for every positive integer t. More generally, for 0< p≤ 1/2, every bipartite graph of edge density at least p, with both classes of size at least 128· p−t, contains Kt,t. This gives bq(t)≤ 128· qt for every integer q≥ 2 and a uniform consequence for Zarankiewicz numbers.
Related
- The three-colour bipartite Ramsey number of sufficiently long even cycles
- The 3-Color 2-Chromatic Gallai-Ramsey Number for Complete Graphs
- The k-color poset Ramsey number of the diamond is 2k
- A Computer-Assisted Proof that R(5,10;5,8)=21 for the Generalized Threshold Ramsey Number
- The Three-Color Generalized Schur Number of x+(k−1)y=z: A Proof for All k from a Critical Set of 33 Polynomials
BibTeX
@misc{person2026another,
title = {{Another proof that the two color bipartite Ramsey number is $O(2^t)$}},
author = {Yury Person},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40288},
eprint = {2609.40288},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40288},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Another proof that the two color bipartite Ramsey number is O(2^t)
AU - Yury Person
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40288
UR - https://arxiv.org/abs/2609.40288
AB - For positive integers t and q let b_q(t) be the smallest integer n so that any coloring of the edges of the complete bipartite graph K_n,n with q colors yields a monochromatic copy of K_t,t. We give an independent proof that b_2(t)≤ 128· 2^t for every positive integer t. More generally, for 0< p≤ 1/2, every bipartite graph of edge density at least p, with both classes of size at least 128· p^−t, contains K_t,t. This gives b_q(t)≤ 128· q^t for every integer q≥ 2 and a uniform consequence for Zarankiewicz numbers.
ER -