Size Ramsey number for complete balanced bipartite graphs
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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}\):
Problem
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. \)
Bibliography  

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), 283293.

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

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

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