\documentclass[12pt]{article}
\usepackage{e-jc,amsmath}
\specs{P3.53}{23(3)}{2016}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

%\documentstyle[12pt]{article}
%\textheight 8in\textwidth 6in\oddsidemargin 0in\evensidemargin 0in
\newtheorem{theorem}{Theorem}\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{fact}{Fact}\newtheorem{conjecture}{Conjecture}
\newtheorem{definition}{Definition}
\def\bs{\bigskip}\def\ms{\medskip}\def\ds{\displaystyle}
\renewcommand{\text}[1]{\quad\mbox{#1}\quad}
\def\beq{\begin{equation}}\def\eeq{\end{equation}}
\def\beqn{\begin{eqnarray}}\def\eeqn{\end{eqnarray}}
\def\pont{\hspace{-6pt}{\bf.\ }}
\def\eps{\varepsilon}\def\ffi{\varphi}
\def\qed{\ifhmode\unskip\nobreak\fi\quad\ifmmode\Box\else$\Box$\fi}

\title{ On the multi-colored Ramsey numbers\\ of paths and even cycles}


\author{G\'{a}bor N. S\'ark\"ozy
\thanks{Research supported in part by
OTKA Grant No. K104343.}\\[-0.8ex]
\small Alfr\'ed R\'enyi Institute of Mathematics\\[-0.8ex]
\small Hungarian Academy of Sciences\\[-0.8ex]
\small Budapest, P.O. Box 127\\[-0.8ex]
\small Budapest, Hungary, H-1364\\
and\\
\small Computer Science Department\\[-0.8ex]
\small Worcester Polytechnic Institute\\[-0.8ex]
\small Worcester, MA, USA 01609\\[-0.8ex]
\small \texttt{gsarkozy@cs.wpi.edu}}

\date{\dateline{Oct 28, 2015}{Sep 20, 2016}{Sep 30, 2016}\\
   \small Mathematics Subject Classifications: 05C55, 05C38.}

\begin{document}
\maketitle


\begin{abstract}
In this paper we improve the upper bound on the multi-color Ramsey
numbers of paths and even cycles. More precisely, we prove the following.
For every $r\geq 2$ there exists an $n_0=n_0(r)$
such that for $n\geq n_0$ we have
$$R_r(P_n) \leq \left( r - \frac{r}{16r^3+1} \right) n.$$
For every $r\geq 2$ and even $n$ we have
$$R_r(C_n) \leq \left( r - \frac{r}{16r^3+1} \right) n + o(n) \text{as}
n\rightarrow \infty.$$ The main tool is a stability version of the
Erd\H{o}s-Gallai theorem that may be of independent interest.
\end{abstract}


\section{Introduction: Ramsey numbers for paths and even cycles}

For graphs $G_1, G_2, \ldots, G_r$, the Ramsey number $R(G_1, G_2,
\ldots, G_r)$ is the smallest positive integer $n$ such that if the
edges of a complete graph $K_n$ are partitioned into $r$ disjoint
color classes giving $r$ graphs $H_1, H_2, \ldots, H_r$, then at
least one $H_i$, $1\leq i \leq r$, has a subgraph isomorphic to
$G_i$. The existence of such a positive integer is guaranteed by
Ramsey's classical result \cite{RA}. The number $R(G_1, G_2, \ldots, G_r)$ is called the Ramsey number for the graphs $G_1, G_2, \ldots, G_r$. If every $G_i$ is the same graph $G$, then we use the
notation $R_r(G)$. There is very little known about $R_r(G)$ for
$r\geq 3$ even for very special graphs (see e.g. \cite{GRS} or
\cite{RAD}). In this paper we consider the case when $G$ is either a path
$P_n$ on $n$ vertices or a cycle $C_n$ for $n$ even. For $r=2$ a
well-known theorem of Gerencs\'er and Gy\'arf\'as \cite{GG} states
that
$$R_2(P_n) = \left\lfloor \frac{3n-2}{2} \right\rfloor.$$
For $r=3$ Faudree and Schelp \cite{FS} conjectured the following
$$R_3(P_n) = \left\{
\begin{array}{l}
2n - 1 \; \; \mbox{for odd} \; n,\\
2n - 2 \; \; \mbox{for even} \; n.
\end{array}\right.$$
In \cite{GRSS} we proved this conjecture for sufficiently large $n$
(but the conjecture is still open for every $n$). For $r\geq 4$ very
little is known about $R_r(P_n)$. We can get a trivial upper bound
by applying the Erd\H{o}s-Gallai extremal theorem (see Lemma
\ref{eg} below) to the spanning subgraph induced
by the edges of the most frequent color: \beq\label{trivi}
R_r(P_n) \leq r n.\eeq As far as we know there is no better bound
known in general even though we believe the truth is close to
$(r-1)n$. The main result of this paper is to improve on
(\ref{trivi}).
\begin{theorem}\label{ut}\pont For every $r\geq 2$ there exists an $n_0=n_0(r)$
such that for $n\geq n_0$ we have
$$R_r(P_n) \leq \left( r - \frac{r}{16r^3+1} \right) n.$$
\end{theorem}
We make no attempt at optimizing the coefficient since it is
probably far from optimal. The goal of this paper is to separate it
from the trivial upper bound. Since in the proof we will only use
the two most frequent colors, there seems to be room for
improvement.

We have a similar result for even cycles. It is believed that the
Ramsey numbers for paths and even cycles are asymptotically the same
via standard methods using the Regularity Lemma \cite{Sz} and the
notion of connected matchings (see Lemma \ref{reg} below). This
method was introduced by {\L}uczak \cite{L} and has been
successfully used in many papers in this area (see for example
\cite{BS}, \cite{FL}, \cite{GRSS}, \cite{KSS} and \cite{LSS}). Using
this method and the Erd\H{o}s-Gallai extremal theorem, one can get an
upper bound for the Ramsey number of even cycles (see \cite{LSS}):
if $n$ is even we have \beq\label{trivi2}R_r(C_n) \leq r n + o(n)
\text{as} n\rightarrow \infty.\eeq Here $r$ is fixed and $n$ is
large. In the other direction, for an even $n$ the following lower
bound is proved in \cite{YYFB}
$$R_r(C_n) \geq (r-1) (n-2) + 2.$$ Here again we believe that the
lower bound is close to the truth. In this paper we improve on
(\ref{trivi2}).
\begin{theorem}\label{kor}\pont For every $r\geq 2$ and even $n$ we have
$$R_r(C_n) \leq \left( r - \frac{r}{16r^3+1} \right) n + o(n) \text{as}
n\rightarrow \infty.$$
\end{theorem}

\noindent After presenting the necessary tools in the next section, we give
the proofs in Section \ref{proofs}.

\section{Definitions and tools}

We let $V(G)$ and $E(G)$ denote the vertex-set and the edge-set of the
graph $G$. For a graph $G$ and a subset $U$ of its vertices,
$G[U]$ is the restriction of $G$ to $U$.
$N_G(v)$ is the set of neighbours of $v\in V(G)$.
Hence $|N_G(v)|=deg_G(v)$, the degree of $v$. In $N_G(v)$ and $deg_G(v)$
we may omit the subscript $G$ if it is clear from the context.
The average degree of a graph $G$ on $n$ vertices
is the average of the degrees in $G$, i.e. $\sum_{v\in V(G)}deg(v)/n$.

The first tool we will need is the classical result of Erd\H{o}s and
Gallai \cite{EG} which determines the maximum number of edges in any
graph on $n$ vertices if it contains no $P_k$.

\begin{lemma}[\cite{EG}]\label{eg}\pont If $G$ is a graph on $n$ vertices
containing no $P_k$, $k\geq 2$, then
$$|E(G)|\leq \frac{k-2}{2} n,$$
with equality if and only if $k-1$ divides $n$ and all connected
components of $G$ are complete graphs on $k-1$ vertices.
\end{lemma}

We will also need a similar result for connected graphs proved by
Kopylov \cite{K} (see also \cite{BGLS} and \cite{FSI} for further
details).

\begin{lemma}[\cite{K}]\label{conn-EG}\pont
Let $G$ be a connected graph on $n$ vertices containing no $P_k$,
$n>k\geq 3$. Then $|E(G)|$ is bounded above by the maximum of
${k-2\choose 2} +(n-k+2)$ and ${\lceil k/2\rceil \choose 2}  +
\lfloor (k-2)/2\rfloor \left(n-\lceil \frac{k}{2} \rceil \right)$.
\end{lemma}

Finally the last lemma provides the fairly standard transition from
paths to even cycles via connected matchings.

\begin{lemma}[see Lemma 8 in \cite{LSS}]\label{reg}\pont
Let a real number $c>0$ be given. If for every $\eps >0$ there exist
a $\delta >0$ and an $n_0$ such that for every even $n>n_0$ and any
graph $G$ with $|V(G)|>(1+\eps )cn$ and $|E(G)| \geq ( 1-\delta )
{|V(G)|\choose 2}$, any $r$-edge-coloring of $G$ has a monochromatic
component containing a matching of $n/2$ edges, then
$$R_r(C_n)\leq (c+o(1))n.$$
\end{lemma}

\section{Proofs}\label{proofs}

\subsection{Proof of Theorem \ref{ut}}

We may assume throughout that $r\geq 4$, since we have precise
results for $r=2$ and $r=3$. We may also assume that $n$ is
sufficiently large compared to $r$. Theorem \ref{ut} follows easily
from the following.

\begin{lemma}\label{ket_szin}\pont For every $r\geq 2$ there exists an $n_0=n_0(r)$
such that for any $r$-colored complete graph on $n\geq n_0$ vertices
one of the two most frequent colors contains a monochromatic path of
length at least $\left(\frac{1}{r} + \frac{1}{16 r^4}\right) n$.
\end{lemma}

Indeed, if we consider an $r$-colored complete graph on at least
$\left( r - \frac{r}{16r^3+1} \right) n$ vertices (where $n$ is
sufficiently large) by Lemma \ref{ket_szin} one of the two most
frequent colors contains a monochromatic path of length at least
$$\left(\frac{1}{r} + \frac{1}{16 r^4}\right) \left(
r - \frac{r}{16r^3+1} \right) n = n,$$ proving Theorem \ref{ut}.

To simplify the notation we put \beq\label{kx} k_r = \left\lceil
\left(\frac{1}{r} + \frac{1}{16 r^4}\right) n\right\rceil \text{and} x_r =
\left\lceil k_r \left(\frac{1}{16r^2} + \frac{1}{8 r^3}\right)
\right\rceil.\eeq

Lemma \ref{ket_szin} in turn will follow from the following lemma
which can be viewed as a stability version of the Erd\H{o}s-Gallai
theorem (Lemma \ref{eg}). Namely, either we have a slightly longer
path than guaranteed by Lemma \ref{eg} or we are close to the
extremal case: there are at most $r$ ``almost-cliques" that cover ``most" of
the graph.

\begin{lemma}\label{struktura}\pont For every $r\geq 2$ there exists an $n_0=n_0(r)$
such that if $G$ is a graph on $n\geq n_0$ vertices and $|E(G)| \geq
\left(\frac{1}{r} - \frac{1}{8 r^5}\right) \frac{n^2}{2}$, then one
of the following two cases must hold: \begin{itemize}
\item[(a)] $G$ contains a path of length at least $k_r$,
\item[(b)] There are at most $r$ connected components $C$ in $G$ such that
for each $C$ we have $|C|\leq k_r+x_r$, together they cover at least
$\left(1-\frac{1}{r}\right) n$ vertices and within each $C$ the
average degree is at least $k_r-x_r$.
\end{itemize}
\end{lemma}

{\bf Proof of Lemma \ref{struktura}:} We may assume that (a) does
not hold, i.e. $G$ does not contain a path of length at least $k_r$,
and we have to show that in this case (b) must be true. Let us take
the connected components of $G$. First we show that we cannot have
large components.

\begin{claim}\label{nagy}\pont For every connected component $C$ of
$G$, we have $|C| \leq k_r + x_r$.
\end{claim}

Assume to the contrary that we have a component $C$ with $|C| > k_r
+ x_r$. Put $n_1=|C|$ and $n_2=|V(G)\setminus C|$. Since $G$ does
not contain a path of length $k_r$, we can apply Lemma \ref{eg} in
$G[V(G)\setminus C]$ and Lemma \ref{conn-EG} in $G[C]$ with
$k=k_r$. Indeed, applying Lemma \ref{conn-EG} in $G[C]$, the number
of edges of $G$ within $C$ is at most 
\begin{align*}
\max \left( \frac{k_r^2}{2}
+ n_1, \frac{k_r^2}{8} + \frac{k_r}{2} \left (n_1- \frac{k_r}{2}
\right) \right) 
&= \max \left( \frac{k_r n_1}{2} - \frac{k_r(n_1-k_r)}{2} + n_1,
\frac{k_r n_1}{2} - \frac{k_r^2}{8}\right) \\
&< \frac{k_r n_1}{2} - \min \left( \frac{k_r x_r}{2},
\frac{k_r^2}{8}\right) + n_1 = \frac{k_r n_1}{2} - \frac{k_r x_r}{2}
+ n_1.
\end{align*}
Here in the last line first we used that $n_1-k_r>x_r$,
then $x_r < \frac{k_r}{4}$ (using (\ref{kx})).

Then by applying Lemma \ref{eg} in $G[V(G)\setminus C]$, the
number of edges of $G$ in $G[V(G)\setminus C]$ is at most
$\frac{k_rn_2}{2}$. Thus altogether the number of edges in $G$ is at
most
\begin{align*}
& \frac{k_r n_1}{2} - \frac{k_r x_r}{2} + n_1 + \frac{k_rn_2}{2}
\leq \frac{k_rn}{2} - \frac{k_r x_r}{2} + n \\
\leq &\left(\frac{1}{r} + \frac{1}{16 r^4}\right) \frac{n^2}{2} + \frac{n}{2} -
\left(\frac{1}{r} + \frac{1}{16 r^4}\right)^2 \left(\frac{1}{16r^2}
+ \frac{1}{8 r^3}\right) \frac{n^2}{2} + n \\
\leq& \frac{1}{r}\frac{n^2}{2} + \frac{1}{16r^4}\frac{n^2}{2} - \frac{1}{16r^4}\frac{n^2}{2} -
\frac{1}{8r^5}\frac{n^2}{2} - \frac{1}{16^2r^8}
\left(\frac{1}{16r^2} + \frac{1}{8 r^3}\right) \frac{n^2}{2} +
\frac{3n}{2} \\
< &\left(\frac{1}{r} - \frac{1}{8 r^5}\right) \frac{n^2}{2}\leq |E(G)|,
\end{align*}
if $n$ is sufficiently large (using (\ref{kx})), a contradiction.
This finishes the proof of Claim \ref{nagy}.

Let us denote by $\cal{C}$ the set of those components $C$ where the
average degree is at least $k_r-x_r$. We will show that this is a
good collection of components for (b) in Lemma \ref{struktura}.
First we show that indeed the components in $\cal{C}$ together cover
at least $\left( 1 - \frac{1}{r}\right)n$ vertices.

\begin{claim}\label{unio}\pont We have $$\sum_{C\in \cal{C}} |C|
\geq \left( 1 - \frac{1}{r}\right)n.$$
\end{claim}

Indeed, we will use a similar argument as above for Claim
\ref{nagy}. Put $n_1=\sum_{C\in \cal{C}} |C|$ and $n_2=|V(G)|-n_1$.
Assume indirectly that $n_2
> \frac{n}{r}$. By applying Lemma \ref{eg} to $G[\bigcup _{C\in \cal{C}} C]$ and using
the upper bound on the average degree in the remaining part, the
number of edges in $G$ is less than
\begin{align*}
& \frac{k_r n_1}{2} + \frac{(k_r-x_r) n_2}{2} = \frac{k_r n}{2} - \frac{x_r
n_2}{2} \\
\leq &\left(\frac{1}{r} + \frac{1}{16 r^4}\right) \frac{n^2}{2} + \frac{n}{2} -
\left(\frac{1}{r} + \frac{1}{16 r^4}\right) \left(\frac{1}{16r^2} +
\frac{1}{8 r^3}\right) \frac{n^2}{2r} \\
\leq &\frac{1}{r}\frac{n^2}{2} + \frac{1}{16r^4}\frac{n^2}{2} - \frac{1}{16r^4}\frac{n^2}{2} -
\frac{1}{8r^5}\frac{n^2}{2} - \frac{1}{16 r^5} \left(\frac{1}{16r^2}
+ \frac{1}{8 r^3}\right) \frac{n^2}{2} + \frac{n}{2} \\
< &\left(\frac{1}{r} - \frac{1}{8 r^5}\right) \frac{n^2}{2}\leq |E(G)|,
\end{align*}
if $n$ is sufficiently large (using (\ref{kx}) and $n_2
> \frac{n}{r}$ in the second line), a contradiction.
This finishes the proof of Claim \ref{unio}.

Finally we show that indeed there are at most $r$ components in
$\cal{C}$.
\begin{claim}\label{r}\pont The number of connected components in
$\cal{C}$ is at most $r$.
\end{claim}

Indeed, we show that we cannot have more than $r$ components in
$\cal{C}$. Assume to the contrary that we have at least $r+1$
components in $\cal{C}$. Since the size of each $C$ in $\cal{C}$ is
at least the average degree in $C$, the number of vertices in $G$ is
at least
\begin{align*}
&(r+1) (k_r-x_r) \geq (r+1) \left(\frac{1}{r} + \frac{1}{16
r^4}\right) \left( 1 - \frac{1}{16r^2} - \frac{1}{8 r^3}\right) n -
2(r+1)\\
 \geq &\left( 1 + \frac{1}{r} - \frac{1}{8r^2} - \frac{1}{4r^3}
\right) n - 2(r+1) > n,
\end{align*}
 if $n$ is sufficiently large (using $r\geq
4$), a contradiction.

Thus indeed the components in $\cal{C}$ satisfy the conditions in
(b), finishing the proof of Lemma \ref{struktura}. \qed

Next we show how Lemma \ref{ket_szin} can be derived from Lemma
\ref{struktura}, finishing the proof.

{\bf Proof of Lemma \ref{ket_szin}:} Consider an $r$-colored graph
$G$ on $n\geq n_0(r)$ vertices, where $n_0(r)$ is chosen sufficiently
large so that Lemma \ref{struktura} and all subsequent inequalities hold.
Let us take a most frequent color,
say red, in $G$. The number of these red edges is at least
\begin{align}\label{piros}
\frac{1}{r} {n\choose 2} \geq \left( \frac{1}{r} -
\frac{1}{8 r^5} \right) \frac{n^2}{2},
\end{align}
 so we may apply Lemma
\ref{struktura} for the red subgraph. If (a) holds then we are done,
therefore we may assume that (b) holds, i.e. there are $r$ red
components with the properties given in (b) in Lemma
\ref{struktura}. Furthermore, we may assume that the number of red
edges is at most $\frac{k_rn}{2}$, since otherwise by Lemma \ref{eg}
we would have (a), i.e. a red path of length at least $k_r$. Let us
take a second most frequent color, say blue. The number of blue
edges is at least
\begin{align*}
&\frac{1}{r-1} \left( {n\choose 2} - \frac{k_rn}{2} \right) \geq
\frac{1}{r-1} \left( \frac{n^2}{2} - \left(\frac{1}{r} + \frac{1}{16
r^4}\right) \frac{n^2}{2} \right) - \frac{n}{r-1} \\
%\beq&\label{kek} 
&= \left(\frac{1}{r} - \frac{1}{16(r-1) r^4}\right)
\frac{n^2}{2} - \frac{n}{r-1} \geq \left( \frac{1}{r} - \frac{1}{8
r^5} \right) \frac{n^2}{2}, \stepcounter{equation}\tag{\theequation}\label{kek}%\eeq
\end{align*}
 so again we may apply Lemma
\ref{struktura} for the blue subgraph as well. If (a) holds then we
are done, therefore we may assume that (b) holds, i.e. there are $r$
blue components with the properties given in (b) in Lemma
\ref{struktura}. We will show that this leads to a contradiction,
i.e. in either the red subgraph or in the blue subgraph we must have
(a).

Consider the at most $r^2$ non-empty ``atoms" determined by the at most $r$
red components and the at most $r$ blue components, i.e. they are all the possible intersections
of one of the at most $r$ red components with one of the at most $r$ blue components. Thus there exists an
atom $A$ such that $A$ is a subset of a red component, it is also a
subset of a blue component and \beq\label{|A|} |A| \geq
\frac{1}{r^2} \left( 1 - \frac{2}{r} \right) n \geq
\frac{n}{2r^2}\eeq (using $r\geq 4$). We will show that both the red
and the blue subgraph contains more than half of the edges within
$A$, a contradiction. Indeed, the number of
missing edges in the red subgraph (and similarly for blue) within
$A$ is at most $x_r(k_r+x_r)$. In order to see this, note that the number
of missing edges in the red
component $C$ containing the atom $A$ is at most
$$\frac{|C| (|C|-(k_r-x_r))}{2} \leq \frac{(k_r+x_r)(k_r+x_r-(k_r-x_r))}{2} = x_r(k_r+x_r)$$
(using $|C|\leq k_r+x_r$ and that the average degree in $C$ is at least $k_r-x_r$),
and then we assume the worst case, namely that all the missing edges in $C$ are missing within $A$. Then
\begin{align*}
x_r (k_r+x_r) \leq& \left(\frac{1}{r} + \frac{1}{16
r^4}\right)^2 \left(\frac{1}{16r^2} + \frac{1}{8 r^3}\right) \left(1
+ \frac{1}{16r^2} + \frac{1}{8 r^3}\right) n^2 + n\\
\leq &\left(\frac{1}{16 r^4} + \frac{1}{8
r^5} + 16 \frac{1}{64 r^6} \right) n^2 + n \leq \left(\frac{1}{16
r^4} + \frac{1}{8 r^5} + \frac{1}{16 r^5} \right) n^2 + n\\
=&\left(\frac{1}{16 r^4} + \frac{3}{16 r^5} \right)n^2 + n < \frac{n^2}{8
r^4} - n \leq \frac{|A|^2}{4} - \frac{|A|}{4} = \frac{1}{2}
{|A|\choose 2},
\end{align*}
 if $n$ is sufficiently large, as claimed. Here we
used (\ref{|A|}), $r\geq 4$ and in the second line for each of the
terms other than the two largest we used the upper bound
$\frac{1}{64 r^6}$. This finishes the proof of Lemma \ref{ket_szin}
and thus Theorem \ref{ut}. \qed

\subsection{Proof of Theorem \ref{kor}}

In light of Lemma \ref{reg} all we need is a ``perturbed" version of
Lemma \ref{ket_szin} where we replace the complete graph with an
almost-complete graph (Lemma \ref{struktura} needs no change).

\begin{lemma}\label{ket_szin_eps}\pont For every $r\geq 2$ there exists an
$n_0=n_0(r)$ and a $\delta=\delta(r)$ such that for any $r$-colored
graph $G$ on $n\geq n_0$ vertices with $|E(G)| \geq (1-\delta )
{n\choose 2}$, one of the two most frequent colors contains a
monochromatic path of length at least $\left(\frac{1}{r} +
\frac{1}{16 r^4}\right) n$.
\end{lemma}

The proof of Lemma \ref{ket_szin_eps} is almost identical to the
proof of Lemma \ref{ket_szin}, in both inequalities (\ref{piros})
and (\ref{kek}) we have room to spare:

$$\frac{1}{r} (1-\delta ) {n\choose 2} \geq \left( \frac{1}{r} - \frac{1}{8 r^5}
\right) \frac{n^2}{2},$$ and
$$\frac{1}{r-1} \left( (1-\delta ){n\choose 2} - \frac{k_rn}{2} \right) \geq
\frac{1}{r-1} \left( \frac{n^2}{2} - \left(\frac{1}{r} + \frac{1}{16
r^4}\right) \frac{n^2}{2} \right) - \frac{n}{r-1} -
\frac{\delta}{r-1} {n\choose 2} $$ $$= \left(\frac{1}{r} -
\frac{1}{16(r-1) r^4}\right) \frac{n^2}{2} - \frac{n}{r-1} -
\frac{\delta}{r-1} {n\choose 2} \geq \left( \frac{1}{r} - \frac{1}{8
r^5} \right) \frac{n^2}{2},$$ if $\delta$ is sufficiently small
compared to $\frac{1}{r}$. The rest of the proof is identical.

To prove Theorem \ref{kor} we apply Lemma \ref{reg} and Lemma
\ref{ket_szin_eps}. Indeed, for an arbitrary $0<\eps <1$ consider an
$r$-colored graph on $N \geq (1 + \eps )\left( r - \frac{r}{16r^3+1}
\right) n$ vertices with $|E(G)| \geq (1-\delta(r) ) {N\choose 2}$
(where $n$ is a sufficiently large even integer and $\delta(r)$ is
from Lemma \ref{ket_szin_eps}). By Lemma \ref{ket_szin_eps} one of
the two most frequent colors contains a monochromatic path of length
at least
$$\left(\frac{1}{r} + \frac{1}{16 r^4}\right) (1 + \eps ) \left(
r - \frac{r}{16r^3+1} \right) n > n.$$ This implies the existence of
a matching covering $n$ vertices in a monochromatic component.
Hence, Lemma \ref{reg} implies that $R_r(C_n)\leq \left( r -
\frac{r}{16r^3+1}+o(1)\right)n$. \qed




\begin{thebibliography}{99}


\bibitem{BGLS} P.N. Balister, E. Gy\H{o}ri, J. Lehel, R.H. Schelp,
Connected graphs without long paths, {\em Discrete Mathematics} 308
(2008), pp. 4487-4494.

\bibitem{BS} F.S. Benevides, J. Skokan, The 3-colored Ramsey number of even
cycles, {\em   Journal of Combinatorial Theory, Ser. B,} 99(4)
(2009), pp. 690-708.

\bibitem{EG} P. Erd\H{o}s, T. Gallai, On maximal paths and circuits
of graphs, {\em Acta Math. Sci. Hungar.} 10 (1959), pp. 337-356.

\bibitem{FS} R.J. Faudree, R.H. Schelp,
Path Ramsey numbers in multicolorings, {\em Journal of Combinatorial
Theory, Ser. B} 19 (1975), pp. 150-160.

\bibitem{FL} A. Figaj, T. {\L}uczak, The Ramsey number
for a triple of long even cycles, {\em Journal of Combinatorial
Theory, Ser. B} 97 (2007), pp. 584-596.

\bibitem{FSI} Z. F\"{u}redi, M. Simonovits, The history of degenerate
(bipartite) extremal graph problems, {\em Bolyai Math. Studies} 25
pp. 169-264, Erd\H{o}s Centennial (L. Lov\'asz, I. Ruzsa, and V. T.
S\'os, Eds.) Springer, 2013. Also see: \arxiv{1306.5167}.

\bibitem{GG} L. Gerencs\'er, A. Gy\'arf\'as,
On Ramsey-type problems, {\em Ann. Univ. Sci. Budapest E\"{o}tv\"{o}s
Sect. Math.} 10 (1967), pp. 167-170.

\bibitem{GRS} R.L. Graham, B.L. Rothschild, J.H. Spencer,
{\em Ramsey Theory}, John Wiley \& Sons, 1990.

\bibitem{GRSS} A. Gy\'arf\'as, M. Ruszink\'o, G.N. S\'ark\"ozy and E.
Szemer\'edi, Three-color Ramsey number for paths,  {\em
Combinatorica}, 27(1) (2007), pp. 35-69.

\bibitem{KSS} Y. Kohayakawa, M. Simonovits. J. Skokan, The
$3$-colored Ramsey number of odd cycles, {\em Journal of
Combinatorial Theory, Ser. B}, to appear.

\bibitem{K} G.N. Kopylov, Maximal paths and cycles in a graph, {\em Dokl. Akad.
Nauk SSSR} 234 (1977), pp. 19-21. (English translation: {\em Soviet
Math. Dokl.} 18(3) (1977), pp. 593-596.)

\bibitem{L} T. {\L}uczak, $R(C_n, C_n, C_n) \leq (4+o(1))n$,
{\em Journal of Combinatorial Theory, Ser. B} 75 (1999), pp. 174-187.

\bibitem{LSS} T. {\L}uczak, M. Simonovits, J. Skokan, On the
multi-colored Ramsey numbers of cycles, {\em Journal of Graph
Theory} 69 (2012), pp. 169-175.

\bibitem{RAD} S.P. Radziszowski, Small Ramsey numbers,
{\em Electronic Journal of Combinatorics}, (2002) DS1.

\bibitem{RA} F.P. Ramsey, On a problem of formal logic,
{\em Proc. London Math. Soc., 2nd Ser.}, 30 (1930), pp. 264-286.

\bibitem{Sz} E. Szemer\'edi, Regular partitions of graphs,
Colloques Internationaux C.N.R.S. $\mbox{N}^{\underline{o}}$ 260
- {\em Probl\`emes Combinatoires et Th\'eorie des Graphes},
Orsay (1976), 399-401.

\bibitem{YYFB} Y. Sun, Y. Yang, F. Xu, B. Li, New lower bounds
on the multicolor Ramsey numbers $R_r(C_{2m})$, {\em Graphs and
Combinatorics} 22(2) (2006), pp. 283-288.

\end{thebibliography}
\end{document}
