\documentstyle[12pt]{article} \textheight 8in\textwidth 6in\oddsidemargin 0in\evensidemargin 0in \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{ 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}} \begin{document} \maketitle \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 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}