The size Ramsey number of paths

Combinatorics Seminar
Event time: 
Thursday, October 24, 2019 - 4:00pm
DL 431
Deepak Bal
Speaker affiliation: 
Montclair University
Event description: 

Given a graph $H$, let $\hat{R}(H)$ be the minimum $m$ such that there exists a graph $G$ with $m$ edges such that in every $2$-coloring of the edges $G$, there is a monochromatic copy of $H$. To prove that $\hat{R}(P_n)>m$, one must show that every graph on $m$ edges can be $2$-colored such that every monochromatic path has order less than $n$. We show that $\hat{R}{P_n} > (3.75 - o(1))n$ thereby improving the previous best-known lower bound of $(2.5 - o(1))n$ due to Dudek and Pralat. We also discuss some results concerning the $r$-color version of the problem. This is joint work with Louis DeBiasio.

Research Area(s):