Size Ramsey number for unions of stars
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)\).
A size Ramsey problem (proposed by Burr, Erdös, Faudree, Rousseau and Schelp [1])
For \( F_1=\cup_{i=1}^s K_{1,n_i} \) and \(F_2=\cup_{i=1}^t K_{1,m_i}\), prove that \[ \hat{r}(F_1,F_2)= \sum\limits_{k=2}^{s+t} l_k \] where \(l_k= \max \{ n_i+m_j1:~i+j=k\}\).It was proved in [1] that
\(\displaystyle \hat{r}(sK_{1,n}, tK_{1,m}) = (m+n1)(s+t1). \)
Bibliography  

1 
S. A. Burr, P. Erdös, R. J. Faudree, C. C. Rousseau and R. H. Schelp,
Ramseyminimal graphs for multiple copies, Nederl. Akad. Wetensch.
Indag. Math. 40 (1978), 187195.
