Problem Statement
Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges such that in any $2$-colouring of the edges of $H$ there is a monochromatic copy of $G$.
Determine\[\hat{R}(K_{n,n}),\]where $K_{n,n}$ is the complete bipartite graph with $n$ vertices in each component.
Determine\[\hat{R}(K_{n,n}),\]where $K_{n,n}$ is the complete bipartite graph with $n$ vertices in each component.
Categories:
Graph Theory Ramsey Theory
Progress
We know that\[\frac{1}{60}n^22^n<\hat{R}(K_{n,n})< \frac{3}{2}n^32^n.\]The lower bound (which holds for $n\geq 6$) was proved by Erdős and Rousseau [ErRo93]. The upper bound was proved by Erdős, Faudree, Rousseau, and Schelp [EFRS78b] and Nešetřil and Rödl [NeRo78].Conlon, Fox, and Wigderson [CFW23] have proved that, for any $s\leq t$,\[\hat{R}(K_{s,t})\gg s^{2-\frac{s}{t}}t2^s,\]and prove that when $t\gg s\log s$ we have $\hat{R}(K_{s,t})\asymp s^2t2^s$. They conjecture that this should hold for all $s\leq t$, and so in particular we should have $\hat{R}(K_{n,n})\asymp n^32^n$.
See also the entry in the graphs problem collection.
Source: erdosproblems.com/560 | Last verified: January 15, 2026