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_j-1:~i+j=k\}\).It was proved in [1] that
\(\displaystyle \hat{r}(sK_{1,n}, tK_{1,m}) = (m+n-1)(s+t-1). \)
Bibliography | |
---|---|
1 |
S. A. Burr, P. Erdös, R. J. Faudree, C. C. Rousseau and R. H. Schelp,
Ramsey-minimal graphs for multiple copies, Nederl. Akad. Wetensch.
Indag. Math. 40 (1978), 187-195.
|