Logo
All Random Solved Random Open
OPEN
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.

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.