Please email any errors or updates to our website support/editor.

PDF files require Adobe Acrobat Reader.

**Fall term update:** visit our COVID-19 Information website for more information.

Please note: The University of Waterloo is closed for all events until further notice.

Thursday, October 25, 2018 — 3:30 PM EDT

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.

Location

MC - Mathematics & Computer Building

5417

200 University Avenue West

Waterloo, ON N2L 3G1

Canada

200 University Avenue West

Waterloo, ON N2L 3G1

Canada

Please email any errors or updates to our website support/editor.

PDF files require Adobe Acrobat Reader.

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1