PreprintCC BY 4.0arXiv
Sharper Zarankiewicz and Diagonal Bipartite Ramsey Bounds
Abstract
We prove that there is an absolute positive constant c such that every bipartite graph with N vertices in each part and at least N2/2 edges contains a complete bipartite graph Kt,t whenever N≥ c 2t. This improves the classical Kővári-Sós-Turán bound requiring N of order $t\,2^t $. As a consequence, the diagonal bipartite Ramsey number has upper bound b(t,t)=O(2t), improving the previous best bound b(t,t) = O(2t log t ) due to Conlon. The proof was found by GPT-6 Astra, and the method will probably have further applications.
Related
BibTeX
@misc{mubayi2026sharper,
title = {{Sharper Zarankiewicz and Diagonal Bipartite Ramsey Bounds}},
author = {Dhruv Mubayi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32937},
eprint = {2609.32937},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32937},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharper Zarankiewicz and Diagonal Bipartite Ramsey Bounds
AU - Dhruv Mubayi
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32937
UR - https://arxiv.org/abs/2609.32937
AB - We prove that there is an absolute positive constant c such that every bipartite graph with N vertices in each part and at least N^2/2 edges contains a complete bipartite graph K_t,t whenever N≥ c 2^t. This improves the classical Kővári-Sós-Turán bound requiring N of order $t\,2^t $. As a consequence, the diagonal bipartite Ramsey number has upper bound b(t,t)=O(2^t), improving the previous best bound b(t,t) = O(2^t log t ) due to Conlon. The proof was found by GPT-6 Astra, and the method will probably have further applications.
ER -