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 $N^2/2$ edges contains a complete bipartite graph $K_{t,t}$ whenever $N\ge 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.