Cycle Ramsey numbers for random graphs

Abstract

Let $C_n$ be a cycle of length $n$. As an application of Szemerédi's regularity lemma, Łuczak ($R(C_n,C_n,C_n)\le (4+o(1))n$, J. Combin. Theory Ser. B, 75 (1999), 174--187) in fact established that $K_{(8+o(1))n}\to (C_{2n+1},C_{2n+1},C_{2n+1})$. In this paper, we strengthen several results involving cycles. Let $\mathcal{G}(n,p)$ be the random graph. We prove that for fixed $0<p\le 1$, and integers $n_1$, $n_2$ and $n_3$ with $n_1\ge n_2\ge n_3$, it holds that for any sufficiently small $\hat{I}´>0$, there exists an integer $n_0$ such that for all integer $n_3>n_0$, we have a.a.s. that \begin{align*} \mathcal{G}((8+δ)n_1,p) \to (C_{2n_1+1},C_{2n_2+1},C_{2n_3+1}). \end{align*} Moreover, we prove that for fixed $0<p\le 1$ and integers $n_1\ge n_2\ge n_3>0$ with same order, i.e. $n_2=\hat{I}˜(n_1)$ and $n_3=\hat{I}˜(n_1)$, we have a.a.s. that \begin{align*} \mathcal{G}(2n_1+n_2+n_3+o(1)n_1,p) \to (C_{2n_1},C_{2n_2},C_{2n_3}). \end{align*} Similar results for the two color case are also obtained.