Title: Some problems on the size Ramsey numbers
| Speaker: | Gholam Reza Omidi |
| Affiliation: | Isfahan University of Technology |
| Room: | MC 5417 |
Abstract: For given simple graphs $G_1$ and $G_2$, the size Ramsey number $\hat{R}(G_1,G_2)$ is the smallest positive integer $m$, where there exists a graph $G$ with $m$ edges such that in any edge coloring of $G$ with two colors red and blue, there is either a red copy of $G_1$ or a blue copy of $G_2$. In this talk, we investigate two research problems on size Ramsey numbers.
In 1983, Beck gave a linear upper bound (in terms of $n$) for $\hat{r}(P_{n})$, where $ P_n $ is a path on $ n $ vertices, giving a positive answer to a question of Erd\H{o}s. Also, Haxell and Kohayakama in 1994 proved that the size-Ramsey number of the cycle $ C_n $ is linear in terms $ n $, however the Szemeredi's regularity lemma is used in their proof and so no specific constant coefficient is provided. Here we give an alternative proof for the linearity of the size Ramsey number of cycles, avoiding the use of the regularity lemma. This result is proved by showing that an Erd\H{o}s-Renyi random graph with suitable edge probability is almost surely a Ramsey graph for a collection of cycles
In 1981, Erd\H{o}s and Faudree investigated the size Ramsey number $\hat{R}(K_n,tK_2)$, where $K_n$ is a complete graph on $n$ vertices and $tK_2$ is a matching of size $t$. They obtained the value of $\hat{R}(K_n,tK_2)$ when $n\geq 4t-1$ as well as for $t=2$ and asked for the behavior of these numbers when $ t $ is much larger than $ n $. In this regard, they posed the following interesting question: For every positive integer $n$, is it true that
$$\lim_{t\to \infty} \frac{\hat{R}(K_n,tK_2)}{t\, \hat{R}(K_n,K_2)}= \min\left\{\dfrac{\binom{n+2t-2}{2}}{t\binom{n}{2}}\mid t\in \mathbb{N}\right\}?$$
We obtain the exact value of $ \hat{R}(K_n,tK_2) $ for every positive integers $ n,t $ and as a byproduct, we give an affirmative answer to the question of Erd\H{o}s and Faudree.