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\H{o}v\'ari-S\'os-Tur\'an 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.