Problem 560

Erdős Problem #560: declared status 'open'. Formalized: no. 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. Current best: 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\H{o}s and Rousseau [ErRo93]. The upper bound was proved by Erd\H{o}s, Faudree, Rousseau, and Schelp [EFRS78b] and Ne\v{s}et\v{r}il and R\"{o}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$. Prize: no. Tags: graph theory, ramsey theory.