\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P18}{20(1)}{2013}

\newtheorem{theorem}{Theorem}\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{proposition}{Proposition}
\newtheorem{fact}{Fact}\newtheorem{conjecture}{Conjecture}
\newtheorem{definition}{Definition}
\def\bs{\bigskip}\def\ms{\medskip}\def\ds{\displaystyle}
\newcommand{\text}[1]{\quad\mbox{#1}\quad}
\def\Pr{{\rm Pr}}
\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{\bf Monochromatic path and cycle partitions\\ in hypergraphs \footnote { 2010 Mathematics Subject Classification: 05C55,
05C38.\hfil\break\noindent The second author was supported in part by
NSF Grant DMS-0968699 and both by OTKA K104373 } }

\author{Andr\'as Gy\'arf\'as\\
\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\\[-0.8ex]
\small \texttt{gyarfas.andras@renyi.mta.hu}\\[-0.8ex]
\and G\'{a}bor N. S\'ark\"ozy\\
\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}\\[-0.8ex]
\small and\\[-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 \\[-0.8ex]
\small \texttt{sarkozy.gabor@renyi.mta.hu}}

\date{\dateline{Aug 16, 2012}{Jan 14, 2013}{Jan 21, 2013}}

\begin{document}
\maketitle

\hyphenation{mono-chromatic}

\begin{abstract}
Here we address the problem to partition edge colored hypergraphs by
monochromatic paths and cycles generalizing a well-known similar
problem for graphs. We show that $r$-colored $r$-uniform complete
hypergraphs can be partitioned into monochromatic Berge-paths of
distinct colors. Also, apart from $2k-5$ vertices, $2$-colored
$k$-uniform hypergraphs can be partitioned into two monochromatic
loose paths. In general, we prove that in any $r$ coloring of a
$k$-uniform hypergraph there is a partition of the vertex set into
monochromatic loose cycles such that their number depends only on
$r$ and $k$.
\end{abstract}


\section{Introduction.}

The following very simple proposition (a footnote in \cite{GGY}) is
our starting point here.

\begin{proposition}\pont\label{start} In any $2$-coloring of the edges of a finite
complete graph the vertices can be partitioned into a red and a blue
path. Here the empty graph and the one-vertex graph is accepted as a
path of any color.
\end{proposition}

There are several extensions and variations of this proposition. A
very nice result of Rado \cite{RA} says that the same holds for
countably infinite graphs for any finite number $r$ of colors: the
vertex set can be partitioned into monochromatic finite or one-way
infinite paths of distinct colors. However, this fails for finite
graphs, even for $r=3$ \cite{GYSSZ2}. The existence of a bound
$f(r)$ for the number of monochromatic paths covering the vertex set
of an $r$-colored finite complete graph was established in
\cite{GYCOV}. Erd\H os, Gy\'arf\'as and Pyber \cite{EGYP} proved the
same result for cycles, i.e. that one can partition the vertex set
to monochromatic cycles so that the number of cycles depends only on
$r$. The bound $O(r^2\log{r})$ of \cite{EGYP} was improved to $O(r\log{r})$ in
\cite{GRSS}. To demonstrate the difference in the difficulty of path
and cycle partitions, we note that Lehel conjectured that
Proposition \ref{start} remains true if paths are replaced with
cycles. It took a long time until the conjecture was resolved, first
for large enough complete graphs \cite{LRS},\cite{A} and finally for
all complete graphs \cite{BT}. Pokrovskiy \cite{PO} recently showed
that $3$-colored complete graphs can be partitioned into three
monochromatic paths as conjectured in \cite{GYCOV}. In \cite{EGYP} it was conjectured that
$r$-colored complete graphs can be partitioned into $r$ monochromatic cycles. For $r=3$ this was asymptotically proved in \cite{GYSSZ2}
but Pokrovskiy \cite{PO} found a counterexample to that conjecture. However, in the counterexample all but one vertex can be covered by
$r$ vertex disjoint monochromatic cycles. Thus a slightly weaker version of the conjecture still can be true.

This paper addresses the hypergraph case. In Section \ref{path} we
prove extensions of Proposition \ref{start} for paths in
hypergraphs. Note there are several known possibilities to
generalize paths in hypergraphs: Berge paths, loose paths and tight
paths are the most frequently studied variations.

A \it Berge path \rm in a $k$-uniform hypergraph is a collection of
$t$ distinct vertices $v_1,\dots, v_t$ and $t-1$ distinct edges
$e_2,\dots e_t$ such that for $i=2,\dots,t$, $\{v_{i-1},v_i\}\subset
e_i$. We extend Proposition \ref{start} for Berge paths by showing
that the vertex set of any $r$-colored $r$-uniform complete
hypergraph can be partitioned into Berge paths of distinct colors
(Theorem \ref{berge}).

 \it A loose path \rm in a
$k$-uniform hypergraph is a sequence of edges, $e_1,\dots,e_t$ such
that for $1\le i< t$,  $e_i\cap e_{i+1}=v_i$ and for $1\le i<j < t$, $e_i\cap e_j=\emptyset$. 
Similarly, in a {\em loose cycle} for $1\le i\le t$,  $e_i\cap
e_{i+1}=v_i$, where $e_{t+1} = e_1$ (and any other pair of edges must be disjoint). A vertex $v\in e_t$ different
from $v_{t-1}$ is called an end point of the loose path. We
conjecture that in every $2$-coloring of the edges of a complete
$k$-uniform hypergraph all but at most $k-2$ vertices can be
partitioned into two monochromatic loose paths of distinct color. We
prove this with a weaker error term in Theorem \ref{looseth} ($2k-5$
instead of $k-2$ thus proving the conjecture only for $k=3$). We
also extend Rado's theorem for loose paths of infinite graphs
(Theorem \ref{looseinf}). For the general case, when the number of
colors and the uniformity are arbitrary, we show in Theorem
\ref{tetel} that for any $r$ coloring of a $k$-uniform hypergraph
there is a partition of the vertex set into at most $c=c(r,k)$
monochromatic loose cycles.


We finish by noting that for the most restrictive generalization of
paths in hypergraphs, tight paths,  practically nothing is known.
\it A tight $k$-uniform path \rm is a sequence of $t$ vertices where
every consecutive set of $k$ vertices forms an edge. It seems
interesting to decide whether there is a partition into a red and a
blue tight path in every $2$-coloring of a complete $3$-uniform
hypergraph. Soukup and Szentmikl\'ossy \cite{SSZ} recently proved
this for the infinite case, extending Rado's theorem to tight paths.

\section{Partitions by monochromatic paths.}\label{path}

Similarly to the graph case, a set of less than $k$ vertices in an edge-colored $k$-uniform
hypergraph is accepted as a path of any color.


\begin{theorem}\pont\label{berge} Suppose that the edges of the complete $r$-uniform
hypergraph $K_n^r$ are colored with $r$ colors. Then $V(K_n^r)$ can
be partitioned into monochromatic Berge paths of distinct colors.
\end{theorem}

\noindent\bf Proof. \rm Apply induction on $n$. Suppose that
$K_n^r\setminus \{v\}$ is partitioned as required. If there is any
color that does not appear in the partition as the color of a Berge
path (or just a path for simplicity), we can extend the partition by
adding $v$ as a path in the missing color. Thus we may assume that
$P_1,P_2,\dots,P_r$ are nonempty Berge paths, $P_i$ has color $i$.
Let $v_i$ be the end point of $P_i$ and set $A_i=\cup_{j=1}^r v_j
\cup \{v\}$. If the edge $f_i=A_i\setminus \{v_i\}$ has color $c\ne
i$ then the partition can be extended by adding $v,f_c$ to $P_c$ and
removing all end points and end edges except at $P_c,P_i$.

Therefore we may assume that $f_i$ is colored with color $i$ for
every $1\le i \le r$. Consider $g=\cup_{j=1}^r v_j$ and assume that
$g$ is colored by color $l$. Now $P_l$ can be extended by two
vertices, $v_p,v$ where $p\ne l$ and with the edges $g,f_l$ of color
$l$. \qed




\begin{conjecture}\pont\label{looseconj}In every $2$-coloring of the
edges of $K_n^k$ there are two disjoint monochromatic loose paths of
distinct colors such that they cover all but at most $k-2$ vertices.
This estimate is sharp for sufficiently large $n$.
\end{conjecture}

The following construction shows that if true, Conjecture
\ref{looseconj} is best possible for $n$ large enough. Let $Q$ be a
vertex set of $(k-1)m+1$ vertices and color all $k$-element subsets
of $Q$ red. Let $S$ be a vertex set of $2(k-1)$ elements such that
$S\cap Q=\emptyset$. Color all uncolored $k$-element subsets of
$Q\cup S$ blue.

First we show that for $m\ge 4(k-1)$ the largest monochromatic
loose path (or just a path for simplicity) leaves at least $2k-3$
vertices uncovered. For the red path this is obvious since
$|S|=2(k-1)> 2k-3$. To ensure this for the blue path, notice that
the longest blue path has $2|S|$ edges thus covers $2|S|(k-1)-|S|+1$
vertices of $Q$. Thus we need
$$|Q|-(2|S|(k-1)-|S|+1)\ge 2k-3$$ which is valid by the assumption $m\ge 4(k-1)$.

We claim that any pair of vertex disjoint  red-blue loose paths 
in the $2$-colored complete $k$-uniform hypergraph on vertex set
$V=S\cup Q$ leaves at least $k-2$ vertices uncovered. If one path in
the path-pair is not proper, i.e. has at most $k-1$ vertices, then
we have one loose path which by the previous paragraph leaves at
least $2k-3$ vertices uncovered and in the other color at most $k-1$
vertices are covered (since it is not proper). Thus at least $k-2$
vertices remain uncovered. On the other hand, if both paths are
proper then they cover together $(k-1)p+2$ vertices for some $p$.
However, we have $(k-1)(m+2)+1$ vertices, thus at least $k-2$
vertices remain uncovered. \qed

Conjecture \ref{looseconj} follows for $k=3$ from the next result
that gives a slightly weaker error term for $k\ge 4$.

\begin{theorem}\pont\label{looseth}In every $2$-coloring of the
edges of $K_n^k$ there are two disjoint monochromatic loose paths of
distinct colors such that they cover all but at most $2k-5$
vertices.
\end{theorem}

\noindent\bf Proof. \rm Take vertex disjoint red and a blue loose
paths $R=e_1,\dots,e_t, B=f_1,\dots,f_s$ such that they cover as
many vertices as possible. Let $U$ be the set of vertices uncovered
by the vertices of the paths $R,B$. Suppose indirectly that $|U|\ge
2k-4$. We may suppose that $R,B$ are both nonempty otherwise any
vertex of $U$ can be added with the appropriate color. Let $v_R,v_B$
be end points of the red and blue path, respectively. Observe that
for an arbitrary set $S\subset U, |S|=k-1$, $e_1=S\cup \{v_R\}$ is a
blue edge and $e_2=S\cup \{v_B\}$ is a red edge, otherwise we get a
contradiction to the maximality of the cover. If $k=2$ then set
$f=\{v_B,v_R\}$ and observe that either $R$ can be replaced by
$R\cup f\cup e_2$ (if $f$ is red) or $B$ can be replaced by $B\cup
f\cup e_1$ (if $f$ is blue) and in both cases the other path is
truncated by removing its last vertex and last edge. This
contradicts the choice of $R,B$ again.


Finally, if $k\ge 3$, there exists $T\subset U, |T|=k-3, T\cap
S=\emptyset$. We can select end points $w_R,w_B$ from $R,B$ so that
$w_R\ne v_R, w_B\ne v_B$. Now set $f=\{w_R,w_B,p\}\cup T$ where
$p\in S$. Again, we get a contradiction by replacing $R$ with $R\cup
f\cup e_2$ (if $f$ is red) or replacing $B$ with $B\cup f\cup e_1$
(if $f$ is blue) and truncating the other path. \qed

It is worth noting that Rado's result can be easily extended to
loose paths of infinite hypergraphs, even for arbitrary number of
colors. (However, for finite graphs we can prove only partitions
into some number of monochromatic paths that depends on $r,k$ only, see Section \ref{exists}.)

\begin{theorem}\pont\label{looseinf}Suppose that the edges of a countably infinite
complete $k$-uniform hypergraph are colored with $r$ of colors. Then
the vertex set can be partitioned into monochromatic finite or
one-way infinite loose paths of distinct colors.
\end{theorem}

\noindent\bf Proof. \rm Let $V$ be the vertex set of a countably
infinite complete $k$-uniform hypergraph with an $r$-coloring. Call
a subset $I$ of colors nice, if there is a set of finite vertex
disjoint loose paths $\{P_i: i\in I\}$ in these colors such that
each $P_i$ has an endpoint $v_i$ and the following property is true:
there is an infinite subset $H$ of vertices such that $H\cap
(\cup_{i\in I} V(P_i))=\emptyset$ and the edge  for any subset
$S\subset H, |S|=k-1$, and for any $i\in I$, $v_i\cup S$ is colored
with color $i$. Nice subsets exists since by Ramsey's theorem for
any vertex $v$ there is an infinite set  $H$ of vertices such that
$v\notin H$ and for any $S\subset H, |S|=k-1$, $v\cup S$ has the
same color $i$. Now color $i$ is a nice set with $P_i=\{v\}$. Let
$I$ be a \it maximal \rm nice set.

We claim that with an arbitrary ordering $w_1,\dots,w_n,\dots$ of
the vertices of $V\setminus \cup_{i\in I} P_i$, every vertex $w_j$
can be added as extension of $\cup_{i\in I} P_i$ and keeping $I$
nice. Suppose $w_j$ is the next vertex to be added.

If $w_j\in H$ then by Ramsey's theorem, there is an infinite subset
$H_1\subset H$ such that $w_j\notin H_1$ and all edges $\{w_j\cup S:
S\subset H_1, |S|=k-1\}$ have the same color, say color $l$.  By the
maximality of $I$, $l\in I$, therefore we can extend $P_l$ with a
new edge $e$ such that $e$ contains the endpoint $v_l$ of $P_l$,
vertex $w_j$ and an arbitrary set $S$ of $k-2$ vertices from $H$
(not containing $w_j$). Let $w_j$ be the new endpoint of the
extended path. Replace $H$ by $H_1\setminus e$ and observe that $I$
is still nice and one of the paths is extended with new endpoint
$w_j$.

The case $w_j\notin H$ is similar, $H_1$ and $l$ can be defined in
the same way. The only difference is that we extend first $P_l$ with
an edge $e=v_l\cup S$ where $S\subset H_1,|S|=k-1$ and then with a
second edge $f=w_j\cup T$ such that $T\subset H_1$ and $|S\cap
T|=1$. Replace $H$ by $H_1\setminus (S\cup T)$ and $I$ is still nice
and one of the paths is extended with new endpoint $w_j$.

Therefore we have a system of $|I|\le r$ vertex disjoint finite or
one-way infinite monochromatic loose paths covering $V$. \qed








\section{Partitions by monochromatic loose cycles.}\label{exists}


\begin{theorem}\pont\label{tetel}
For all integers $r\ge 1,k \geq 3$ there exists a constant
$c=c(r,k)$ such that in every $r$-coloring of the edges of the
complete $k$-uniform hypergraph $K_n^k$  the vertex set can be
partitioned into at most $c(r,k)$ vertex disjoint monochromatic
loose cycles.
\end{theorem}


\noindent\bf Proof. \rm The proof follows the method of \cite{EGYP}
and uses the linearity of Ramsey numbers of hypergraphs with bounded
degree, see \cite{CFS} and also \cite{I}, \cite{NORS}, \cite{CFKO}, \cite{CFKO2}.
Since this bound is quite weak the resulting bound $c(r,k)$ is quite
weak. It would be desirable to improve on this bound.

A special $k$-uniform hypergraph, the \it crown \rm is defined as
follows. Consider a $k$-uniform loose cycle $C$ with edges $e_i$,
$i=1,2,\dots, t$, the {\em base of the crown}. There are $t$ further
vertices, {\em the rim of the crown}: for each $i$ let $v_i$ be a
new vertex (not in $C$) and add all new edges in the form
$\{v_i,x_1,x_2,\dots,x_{k-1}\}$ for all $x_1\in e_i$, where
$x_1,x_2, \ldots , x_{k-1}$ are consecutive vertices on $C$. Thus at
each $v_i$ we add $k$ edges. Finally we add all missing consecutive
$k$-sets on $C$ to the crown.

Thus a crown has $t(k-1)+t=tk$ vertices, $t(k-1)+tk$ edges and  its
maximum degree is $2k-1$. Therefore, by the result cited above, the
$r$-color Ramsey number of a crown is linear thus there is  a
suitable function $f(r,k)$ such that in every $r$-coloring of the
edges of $K_n^k$ there is a monochromatic crown with at least
$n/f(r,k)$ vertices. We observe the following important property of
crowns.

\begin{lemma}\pont\label{crown} Suppose that $H$ is a hypergraph obtained from a crown by removing an arbitrary subset of
the vertices of its rim together with all edges incident to the
removed vertices. Then the vertices of $H$ can be partitioned into a
loose cycle and at most $k-2$ vertices.
\end{lemma}

\noindent\bf Proof. \rm  Suppose that $H$ contains $p$ vertices from
the rim. By removing at most $k-2$ vertices of $H$ from the rim, we
may reduce $H$  so that $|V(H)|$ is divisible by $k-1$. Now it is
easy to see that the reduced hypergraph $H$ has a spanning loose
cycle.  Indeed, let $w_1,\dots,w_q$ be the vertices of $H$ on the
rim in cyclic order. (In case $H$ has no vertices left on the rim,
then we are done immediately.) Start with the edge $f_1$ of $H$
containing $w_1$ and the first $k-1$ vertices of the edge of $C$
associated to $w_1$. The next edge will be $k$ consecutive vertices
on $C$ starting with the last vertex of $f_1$ on $C$. Then continue
by forming a loose path $P$ containing edges $f_1,\dots$ along $C$
by adding $k$-element sets of $C$ in consecutive position, the next
one always intersecting the previous one in exactly one vertex,
until it first intersects an edge $e$ of $C$ associated to $w_2$. At
this point we continue $P$ with the edge $f_2$ that contains $w_2$,
the last vertex of $P\cap e$ on $C$ and $k-2$ further consecutive
points on $C$. We continue in this fashion. Because the number of
vertices of $H$ on the rim divisible by $k-1$, $P$ closes into a
loose cycle spanning the reduced $H$. This loose cycle and the at
most $k-2$ removed vertices give the required partition. \qed

Now consider an $r$-coloring of the edges of the complete
$k$-uniform hypergraph $K=K_n^k$. Select a monochromatic crown $T$
with $|T|\ge n/f(r,k)$. Set $R=V(K)\setminus V(T)$ and find
consecutively monochromatic vertex disjoint loose cycles in $R$, at
each step selecting a largest possible one. There is always one
which is at least $n/f(r,k)$ proportion of the remaining uncovered
part, because a loose cycle has maximum degree two. (Better bounds exist, however, for easier computation we just use
$f(r,k)$ at each step.) After $s$ steps we are left with an
uncovered subset $X$. We shall fix $s$ so that the following lemma
can be applied.

\begin{lemma}\pont\label{smallX} Suppose $X,Y$ are subsets of vertices in an $r$-colored complete $k\ge 3$-uniform
hypergraph $H$ such that $|X|\le {|Y|\over 2r(k-2)^2}$ and
$2(k-3)\le |Y|$. Then there are at most $cr^2 \log (r)$ pairwise
disjoint monochromatic loose cycles whose vertices cover $X$.
\end{lemma}

\noindent\bf Proof. \rm  We define an $r$-edge-colored complete
graph $G$ on the vertex set $X$ as follows: $u,v\in X$ are adjacent
by an edge of color $i$ if at least ${{|Y|\choose k-2}\over r}$
edges of $H$ are colored with color $i$. Applying the main result of
\cite{EGYP} the vertex set of $G$ can be covered by at most
$cr^2\log(r)$ vertex disjoint monochromatic cycles. We try to make
loose cycles from these graph cycles by extending each edge of
these cycles with $k-2$ vertices to form a hyperedge of the same
color. To achieve this we have to make the extension so that the
$(k-2)$-sets of $Y$ used are pairwise disjoint. The definition of
the edge colors allows us to perform this extension greedily. Indeed,
assume that we have the required extension for some number of edges
and $e$ is the next edge to be extended. Since the cycle partition
of $G$ has at most $|X|$ edges, if the $(k-2)$-subsets of $Y$ used
so far cover $U\subset Y$, then $|U|<|X|(k-2)$. However, at least
${{|Y|\choose k-2}\over r}$ edges of $H$ are colored with the color
of $e$. Overestimating the number of $(k-2)$-subsets of $Y$
intersecting $U$ by $|U|{|Y|\choose k-3}$, we get

$$|U|{|Y|\choose k-3}<|X|(k-2){|Y|\choose k-3}.$$
We claim that
$$|X|(k-2){|Y|\choose k-3} \leq {{|Y|\choose k-2}\over r},$$
i.e. we have an extension that is disjoint from $U$, as desired.
Indeed, otherwise we get
$$\frac{|Y|}{2r(k-2)}\leq \frac{|Y|-k+3}{r(k-2)} < |X|(k-2),$$
contradicting the assumptions of the lemma. \qed

In order to apply Lemma \ref{smallX} we wish to choose $s$ such that
for the remaining set $X$ of vertices we get
$$|X|\leq \frac{1}{2r(k-2)^2} \frac{n}{kf(r,k)}.$$
Then indeed the conditions of Lemma \ref{smallX} are satisfied if we
choose $Y$ to be the rim of the monochromatic crown $T$ found in the
first step since then $|Y|\geq \frac{n}{kf(r,k)}$.


Since after $s$ steps at most
$$(n-|V(T)|)\left(1 - \frac{1}{f(r,k)}\right)^s$$ vertices are left
uncovered, we have to choose $s$ to satisfy
$$(n-|V(T)|)\left(1 -
\frac{1}{f(r,k)}\right)^s \leq \frac{1}{2r(k-2)^2}
\frac{n}{kf(r,k)}.$$ This inequality is certainly true if
$$\left(1 -
\frac{1}{f(r,k)}\right)^s \leq \frac{1}{2rk^3f(r,k)},$$ which in
turn is true using $1-x\leq e^{-x}$ if
$$e^{-\frac{s}{f(r,k)}} \leq \frac{1}{2rk^3f(r,k)}.$$
This shows that we can choose $s = \lceil f(r,k) \log (2rk^3f(r,k)
\rceil$.

Thus the total number of vertex disjoint monochromatic loose cycles
we used to partition the vertex set of $K_n^k$ is at most
$$\lceil f(r,k) \log (2rk^3f(r,k)\rceil + c r^2 \log (r) + k - 1
=c(r,k),$$ finishing the proof. \qed




\begin{thebibliography}{99}

%\bibitem{AS} N. Alon, J.H. Spencer, {The Probabilistic Method}, John
%Wiley and Sons, 1991.

\bibitem{A} P. Allen, Covering two-edge-coloured complete graphs with two disjoint
monochromatic cycles, {\em Combinatorics, Probability and
Computing,}  17(4), 2008, pp. 471--486.


\bibitem{BT} S. Bessy, S. Thomass\'e, Partitioning a graph into a cycle and an anticycle,
a proof of Lehel's conjecture, {\em   Journal of Combinatorial
Theory, Series B,} 100(2), 2010, pp. 176--180.


%\bibitem{B} B. Bollob\'as, {\em Extremal Graph Theory},
%Academic Press, London (1978).

\bibitem{CFKO} O. Cooley, N. Fountoulakis, D. K\"uhn, D. Osthus, $3$-uniform hypergraphs of bounded degree have linear Ramsey numbers, {\em J. of Combinatorial Theory B} {\bf 98} (2008) 484--505.

\bibitem{CFKO2} O. Cooley, N. Fountoulakis, D. K\"uhn, D. Osthus, Embeddings and Ramsey numbers of sparse $k$-uniform hypergraphs, {\em Combinatorica} {\bf 29} (2009) 263--297


\bibitem{CFS} D. Conlon, J. Fox, B. Sudakov, Ramsey numbers of sparse hypergraphs, {\em Random Structures and Algorithms} {\bf 35} (2009) 709--727.

%\bibitem{D} R. Diestel, {\em Graph Theory}, Springer-Verlag, New
%York (1997).

%\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{EGYP} P. Erd\H{o}s, A. Gy\'{a}rf\'{a}s, and L. Pyber,
Vertex coverings by monochromatic cycles and trees, {\em Journal
of Combinatorial Theory}, Ser. B 51, 1991, pp. 90--95.

\bibitem{G} W.T. Gowers, Hypergraph regularity and the
multidimensional Szemer\'edi Theorem, {\em Ann. of Math.} (2) 166
(2007), no. 3, pp. 897--946.

\bibitem{GGY} L. Gerencs\'er, A. Gy\'arf\'as, On Ramsey type problems, {\em Ann. Univ. Sci.
E\"otv\"os, Budapest} {\bf 10} (1967) 167--170.


\bibitem{GYCOV} A. Gy\'{a}rf\'{a}s, Covering complete graphs by monochromatic
paths, in {\em Irregularities of Partitions}, Algorithms and
Combinatorics, Vol. 8, Springer-Verlag, 1989, pp. 89--91.


\bibitem{GRSS} A. Gy\'arf\'as, M. Ruszink\'o, G. N. S\'ark\"ozy and E.
Szemer\'edi, An improved bound for the monochromatic cycle partition
number, {\em Journal of Combinatorial Theory, Series B,} 96(6),
2006, pp. 855--873.

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

%\bibitem{GYSSz1} A. Gy\'arf\'as, G. N. S\'ark\" ozy, E. Szemer\'edi,
%The Ramsey number of diamond-matchings and loose cycles in
%hypergraphs, {\em Electronic Journal of Combinatorics} 15 (1),
%(2008), \#R126.

\bibitem{GYSSZ2}A. Gy\'arf\'as, M. Ruszink\'o, G. N. S\'ark\"ozy and E.
Szemer\'edi, Partitioning $3$-colored complete graphs into three
monochromatic cycles, {\em Electronic J. of Combinatorics} {\bf 18} (2011) P53.



%\bibitem{H} P. Haxell, Partitioning complete bipartite graphs by
%monochromatic cycles, {\em Journal of Combinatorial Theory}, Ser.
%B 69, 1997, pp. 210-218.

%\bibitem{HLPRRSS1} P. Haxell, T. Luczak, Y. Peng, V. R\"odl, A.
%Rucinski, M. Simonovits, J. Skokan, The Ramsey number for hypergraph
%cycles I, {\em Journal of Combinatorial Theory, Ser. A} 113 (2006),
%pp. 67-83.

\bibitem{I} Y. Ishigami, Linear Ramsey numbers for bounded-degree hypergraphs, {\em Electronic Notes in Discrete Mathematics} {\bf 29} (2007) 47-51.

%\bibitem{K} P. Keevash, A hypergraph blow-up lemma, to appear in
%{\em Random Structures and Algorithms}.

%\bibitem{KKMO} P. Keevash, D. K\"uhn, R. Mycroft, D. Osthus, Loose
%Hamilton cycles in hypergraphs, to appear in {\em Discrete
%Mathematics}.

%\bibitem{KSSz2} J. Koml\'os, G. N. S\'ark\"ozy and E. Szemer\'edi,
%Blow-up Lemma, {\em Combinatorica} 17 (1997), pp. 109-123.

%\bibitem{KSSz3} J. Koml\'os, G. N. S\'ark\"ozy and E. Szemer\'edi,
%An algorithmic version of the Blow-up Lemma,
%{\em Random Structures and Algorithms} 12 (1998), pp. 297-312.

%\bibitem{KS} J. Koml\'os, M. Simonovits,
%Szemer\'edi's Regularity Lemma and its applications
%in graph theory, in {\em Combinatorics, Paul Erd\H{o}s is
%Eighty} (D. Mikl\'os, V.T. S\'os, and T. Sz\H{o}nyi, Eds.),
%Bolyai Society Math. Studies, Vol.2, pp. 295-352, Budapest, 1996.

%\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{LRS} T. \L uczak, V. R\"{o}dl, E. Szemer\'edi,
Partitioning two-colored complete graphs into two monochromatic
cycles, {\em Combinatorics, Probability and Computing}, 7, 1998, pp.
423-436.

%\bibitem{M} W. Mader, Existenz $n$-fach zusammenh\"angen der
%Teilgraphen in Graphen gen\"ugend gro\ss er Kantendichte, {\em
%Abh. Math. Sem. Univ. Hamburg} 37 (1972), pp. 86-97.

%\bibitem{MSz} R. Martin and E. Szemer\'edi, Quadripartite version of the
%Hajnal-Szemer\'edi Theorem, Submitted to a special edition of {\em
%Discrete Mathematics} in honor of Mikl\'os Simonovits.

\bibitem{NORS} B. Nagle, S. Olsen, V. R\"odl, M. Schacht, On the Ramsey number of sparse $3$-graphs, {\em Graphs and Combinatorics} {\bf 24} (2008) 205--228

\bibitem{PO} A. Pokrovskiy, Partitioning edge-coloured complete graphs into monochromatic cycles and paths, ArXiv:1205.5492v1

\bibitem{RA} R. Rado, Monochromatic paths in graphs, {\em Annals of
Discrete Mathematics} {\bf 3} (1987) 89-91.


%\bibitem{RRS} V. R\"odl, A. Ruci\'nski, E. Szemer\'edi, An
%approximate Dirac-type theorem for $k$-uniform hypergraphs, {\em
%Combinatorica} 28 (2) (2008), pp. 229-260.

%\bibitem{RS} V. R\"odl, M. Schacht, Regular partitions of hypergraphs:
%Regularity Lemmas, {\em Combinatorics, Probability and Computing},
%16 (2007), pp. 833-885.

%\bibitem{RSK} V. R\"{o}dl, J. Skokan, Regularity Lemma for uniform
%hypergraphs, {\em Random Structures and Algorithms} 25 (1) (2004),
%pp. 1-42.

%\bibitem{SS} G. N. S\'ark\"ozy, S. Selkow, Vertex partitions by
%connected monochromatic $k$-regular graphs, {\em Journal of
%Combinatorial Theory, Ser. B} 78 (2000), pp. 115-122.

%\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{SSZ} L. Soukup, Z. Szentmikl\'ossy, in preparation.
\end{thebibliography}
\end{document}
