Size Ramsey number for complete balanced bipartite graphs

The size Ramsey number \( \hat{r}(G,H)\) is the least integer \( m\) for which there exists a graph \( F\) with \( m\) edges so that in any coloring of the edges of \( F\) in red and blue, there is always either a red copy of \( G\) or a blue copy of \( H\). Sometimes we write \( F \rightarrow (G,H)\) to denote this. For \( G=H\), we denote \( \hat{r}(G,G)\) by \( \hat{r}(G)\).

For the complete graph \( K_n\), Erdös, Faudree, Rousseau and Schelp [1] proved that

\(\displaystyle \hat{r}(K_n) = \binom {r(n)}{2}. \)

They asked the following size Ramsey problem for \( K_{n,n}\):


Determine \( \hat{r}(K_{n,n})\).

Erdös, Faudree, Rousseau and Schelp [4] and Nešetril and Rödl [3] proved the following upper bound for \( \hat{r}(K_{n,n})\):

\(\displaystyle \hat{r}(K_{n,n}) < \frac 3 2 n^3 2^n.\)

For the lower bound, Erdös and Rousseau [2] proved by probabilistic methods that for \( n \geq 6\),

\(\displaystyle \hat{r}(K_{n,n}) > \frac 1 {60} n^2 2^n. \)

1 P. Erdös, R. Faudree, C. C. Rousseau and R. H. Schelp, Ramsey numbers for brooms, Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982), Congr. Numer. 35 (1982), 283-293.

2 P. Erdös and C. C. Rousseau. The size Ramsey number of a complete bipartite graph, Discrete Math. 113 (1993), 259-262.

3 J. Nešetril and V. Rödl. The structure of critical graphs, Acta. Math. cad. Sci. Hungar. 32 (1978), 295-300.

4 P. Erdös, R. J. Faudree, C. C. Rousseau and R. H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978), 145-161.