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.