#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

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

- Current students (3)
- Future students (2)
- Faculty (3)
- Staff (1)

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

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

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Office of Indigenous Relations.