A note on the size Ramsey number of powers of paths

Abstract

Let $r\ge 3$ be an integer such that $r-2$ is a prime power and let $H$ be a connected graph on $n$ vertices with average degree at least $d$ and $\alpha (H)\le \beta n$, where $0<\beta <1$ is a constant. We prove that the size Ramsey number \[ \hat{R}({H};r) > \frac{nd}{2}{(r - 2)^2} - C\sqrt n \] for all sufficiently large $n$, where $C$ is a constant depending only on $r$ and $d$. In particular, for integers $k\ge 1$, and $r\ge 3$ such that $r-2$ is a prime power, we have that there exists a constant $C$ depending only on $r$ and $d$ such that $\hat{R}(P_n^k;r)>kn(r-2{)}^2-C\sqrt{n}-\frac{(k^2+k)}{2}(r-2{)}^2$ for all sufficiently large $n$, where $P_n^k$ is the $kth$ power of $P_n$. We also prove that $\hat{R}(P_n,P_n,P_n)<764.1n$ for sufficiently large $n$. This result improves some results of Dudek and Prałat (\emph{SIAM J. Discrete Math.}, 31 (2017), 2079--2092 and \emph{Electron. J. Combin.}, 25 (2018), no.3, # P3.35).

9 pages, 1 figure