A note on multicolor Ramsey number of small odd cycles versus a large clique

Abstract

Let $R_k(H;K_m)$ be the smallest number $N$ such that every coloring of the edges of $K_N$ with $k+1$ colors has either a monochromatic $H$ in color $i$ for some $1⩽i⩽k$, or a monochromatic $K_m$ in color $k+1$. In this short note, we study the lower bound for $R_k(H;K_m)$ when $H$ is $C_5$ or $C_7$, respectively. We show that \begin{equation*} R_{k}(C_5;K_m)=Ω(m^{\frac{3k}{8}+1}/(\log{m})^{\frac{3k}{8}+1}), \end{equation*} and \begin{equation*} R_{k}(C_7;K_m)=Ω(m^{\frac{2k}{9}+1}/(\log{m})^{\frac{2k}{9}+1}), \end{equation*} for fixed positive integer $k$ and $m\to \infty$. These slightly improve the previously known lower bound $R_k(C_{2\ell +1};K_m)=\Omega (m^{\frac{k}{2\ell -1}+1}/(\log m{)}^{k+\frac{2k}{2\ell -1}})$ obtained by Alon and Rödl. The proof is based on random block constructions and random blowups argument.

References in corpus (1)

• An improved lower bound for multicolor Ramsey numbers and the half-multiplicity Ramsey number problem