Cycle Ramsey numbers for random graphs

MaRDI QIDQ6306190zbMATH OpenFDO

Authors Meng Liu, Yusheng Li, Qizhong Lin, Chunlin You

Publication date 3 September 2018

Abstract: Let $C_n$ be a cycle of length $n$. As an application of Szemer'{e}di's regularity lemma, {L}uczak ($R(C_n,C_n,C_n)leq(4+o(1))n$, J. Combin. Theory Ser. B, 75 (1999), 174--187) in fact established that $K_{(8+o(1))n}o(C_{2n+1},C_{2n+1},C_{2n+1})$. In this paper, we strengthen several results involving cycles. Let $mathcalG(n,p)$ be the random graph. We prove that for fixed $0<ple1$, 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 $delta>0$, there exists an integer $n_0$ such that for all integer $n_3>n_0$, we have a.a.s. that �egin{align*} mathcal{G}((8+delta)n_1,p) o (C_{2n_1+1},C_{2n_2+1},C_{2n_3+1}). end{align*} Moreover, we prove that for fixed $0<ple1$ and integers $n_{1}ge{n}_{2}ge{n}_3>0$ with same order, i.e. $n_2=Theta(n_1)$ and $n_3=Theta(n_1)$, we have a.a.s. that �egin{align*} mathcal{G}(2n_1+n_2+n_3+o(1)n_1,p) o (C_{2n_1},C_{2n_2},C_{2n_3}). end{align*} Similar results for the two color case are also obtained.

This page was built for publication: Cycle Ramsey numbers for random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6306190)