\documentclass[12pt,reqno]{article} %\documentstyle[12pt]{article} \usepackage{e-jc,amsmath,amsthm,amssymb} \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} \newtheorem{question}{Question} \def\bs{\bigskip}\def\ms{\medskip}\def\ds{\displaystyle} \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 loose-cycle partitions in hypergraphs \footnote {The authors were supported in part by OTKA Grant No. K104343.} } \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{2014}{2014}\\ \small Mathematics Subject Classification: 05C38, 05C55} \begin{document} \maketitle \begin{abstract} In this paper we study the monochromatic loose-cycle partition problem for non-complete hypergraphs. Our main result is that in any $r$ coloring of a $k$-uniform hypergraph with independence number $\alpha$ there is a partition of the vertex set into monochromatic loose cycles such that their number depends only on $r$, $k$ and $\alpha$. We also give an extension of the following result of P\'osa to hypergraphs: the vertex set of every graph $G$ can be partitioned into at most $\alpha(G)$ cycles, edges and vertices. \end{abstract} \section{Introduction} It was shown in \cite{EGYP} that the vertex set of any $r$-edge-colored complete graph can be partitioned into monochromatic cycles and vertices so that their number depends only on $r$. The best known bound ($cr\log(r)$) is in \cite{GRSS}. This result from \cite{EGYP} has been extended into two directions. In \cite{SG} it was shown that for an arbitrary $r$-edge-colored graph $G$, $V(G)$ can be partitioned into monochromatic cycles so that their number depends only on the independence number $\alpha(G)$ and $r$. In \cite{GYS} the result was extended to $k$-uniform hypergraphs by replacing cycles with {\em loose cycles} (where only cyclically consecutive edges intersect and in exactly one vertex). In this paper, using an extension of Brooks' theorem for hypergraphs (see Claim \ref{uresek} below), we show that both extensions can be done simultaneously. A subset of vertices in a hypergraph is called {\em independent} if it does not contain any edge from $H$ and the {\em independence number of a hypergraph $H$}, $\alpha(H)$, is defined as the maximum cardinality of an independent set in $H$. \begin{theorem}\pont\label{tetel} For all integers $r\ge 1,k \geq 2, \alpha\ge k-1$ there exists a constant $c=c(r,k,\alpha)$ such that in every $r$-coloring of the edges of a $k$-uniform hypergraph $H$ with independence number $\alpha(H)=\alpha$ the vertex set can be partitioned into at most $c(r,k,\alpha)$ vertex disjoint monochromatic loose cycles. \end{theorem} Concerning the best possible value of $c(r,k,\alpha)$, it was conjectured by Lehel that $c(2,2,1)=2$, proved first for large enough complete graphs in \cite{LRS}, \cite{A} then in general in \cite{BT}. The conjecture $c(3,2,1)=3$ from \cite{EGYP} was proved asymptotically in \cite{GYSSZ2} but its sharp form is refuted by Pokrovskiy \cite{PO}. A well-known result of P\'osa \cite{POS} (see also Exercise 8.3 in \cite{LO}) states that $c(1,2,\alpha)=\alpha$, i.e. every graph $G$ can be partitioned into at most $\alpha(G)$ cycles (where we accept a vertex and an edge as a cycle). Perhaps this can be extended as follows. \begin{conjecture}\pont\label{loose} Is $c(1,k,\alpha)=\alpha$, i.e. can one partition every $k$-uniform hypergraph $H$ into at most $\alpha(H)$ loose cycles? Here (similarly to P\'osa's theorem) vertices and subsets of hyperedges are accepted as loose cycles. \end{conjecture} It is worth noting that a positive answer to Conjecture \ref{loose} easily follows by induction on $\alpha(H)$ for loose paths (instead of loose cycles). Indeed, suppose that $P$ is a loose path of maximum length in a $k$-uniform hypergraph $H$ and $H^*$ is the subhypergraph of $H$ induced by $V(H)\setminus V(P)$. Then $\alpha(H^*)<\alpha(H)$, because any independent set of $H^*$ is extended to an independent set of $H$ by any end vertex of $P$. We prove a result that is weaker than Conjecture \ref{loose} (but still extends P\'osa's theorem), replacing loose cycles by {\em weak cycles} where only cyclically consecutive edges intersect but their intersection size is not restricted. \begin{theorem}\pont\label{weakcycle} The vertex set of every $k$-uniform hypergraph $H$ can be partitioned into at most $\alpha(H)$ vertex disjoint vertices, edges and weak cycles. \end{theorem} \noindent {\bf Proof.} We prove by induction on $\alpha(H)$ (following the proof of P\'osa's theorem in \cite{LO}). If $\alpha(H)=1$ then $H$ has one vertex (and no edge), it covers the vertex set. Let $t$ be the largest integer such that $H$ has a weak path $P$ with $t$ edges, $e_1,\dots,e_t$. If $t=0$, i.e. $H$ has no edges at all, then $|V(H)|=\alpha(H)$ vertices give the required partition. Suppose $t\ge 1$, we may assume that $V(P)=\{1,2,\dots s\}$ and all edges of $P$ are formed by $k$ consecutive numbers. Set $Y=V(P)\setminus e_t,M=e_{t-1}\cap e_t$ and $$F_1=\{e\in E(H): s\in e,e\cap M=\emptyset.\}$$ Assume that $F_1$ is nonempty, observe that from the choice of $t$ every $f\in F_1$ must intersect $Y$. Let $x_f$ be the largest element of $Y\cap f$ and select an $f^*\in F_1$ for which $x^*=x_f^*$ is minimum. If $P$ has one edge that contains $x^*$ let $g$ be that edge and if $P$ has two edges containing $x^*$ let $g$ be the edge ``to the right''. Remove all vertices of the weak cycle $C$ with edges $f^*,g,\dots,e_t$ and observe that from the definition of $f^*$, for any independent set $A$ of the subhypergraph of $H$ spanned by the edges of $H$ inside $V(H)\setminus V(C)$, $A\cup s$ is independent in $H$. Thus $\alpha(V(H)\setminus C)<\alpha(H)$ and by induction we we have the required partition on $V(H)\setminus V(C)$, and the weak cycle $C$ extends it to the required partition of $H$. Therefore we may assume that $F_1$ has no edges, thus every edge of $$F_2=\{e\in E(H): s\in e,e\ne e_t\}$$ must contain at least one vertex of $M$. Suppose that $F_2$ is nonempty, $f\in F_2$. Consider the two-edge weak cycle $C$ with edges $e_t$ and $f$. Now we claim that for any independent set $A$ of the subhypergraph of $H$ spanned by the edges of $H$ inside $V(H)\setminus V(C)$, $A\cup s$ is independent in $H$. Indeed, if there is an edge $h\in H$ such that $h\subset A\cup \{s\}$ then $h\in F_1$, contradicting to the assumption that $F_1=\emptyset$. Thus, by induction we have the required partition on $V(H)\setminus V(C)$, and the two-edge cycle $C$ extends it to the required partition of $H$. We may assume therefore that $F_1\cup F_2=\emptyset$, thus the only edge of $H$ that contains $s$ is $e_t$. Now we set $C=e_t$ and obviously any independent set $A$ of the subhypergraph of $H$ spanned by the edges of $H$ inside $V(H)\setminus V(C)$, $A\cup s$ is independent in $H$. Thus, by induction we have the required partition on $V(H)\setminus V(C)$, and the one-edge weak cycle $C$ extends it to the required partition of $H$. \qed An immediate corollary of Theorem \ref{weakcycle} is that any Steiner system $S$ ($k$-uniform hypergraph in which any pair of vertices is covered by exactly one edge) can be partitioned into at most $\alpha(S)$ vertices, edges and loose cycles (since a weak cycle must be a loose cycle in a Steiner system). However, probably stronger statements hold for them, for example for $k=3$ we state the following conjecture. \begin{conjecture}\pont\label{stenerloose} Every Steiner triple system can be partitioned into at most two loose cycles (a vertex or an edge is also acceptable). \end{conjecture} Note that one loose cycle cannot cover the vertices of a Steiner triple system, since a loose cycle has an even number of vertices. However, it is possible that there exists a loose cycle covering all but one vertex. A well-known construction $S^*$ starts from an STS $S$ on $n$ vertices and extends it to an STS on $2n+1$ vertices by adding a set $A$ of $n+1$ new points with a factorization and each point of $S$ is extended to a set of triples with one of the factors of the factorization. A cycle in $A$ formed by $n$ edges from different factors would give the required loose cycle. However, it is not known whether such a cycle exists in every factorization. Finally, we note that Steiner triple systems always contain Hamiltonian Berge cycles. A {\em Berge cycle} in a hypergraph is a cyclic sequence of $n$ (distinct) vertices and $n$ distinct edges, each covering two cyclically consecutive vertices. Since in a Steiner triple system $S$ every pair of vertices is covered by a unique triple, a Hamiltonian Berge cycle is a cyclic permutation of the points of $S$ such that no triple of $S$ is in consecutive positions. Equivalently, a Berge cycle in $S$ is a tight cycle (where every set of three consecutive vertices forms an edge) in the complement of $S$. The existence of a tight Hamiltonian cycle in the complement an STS follows from the fact that every codegree is very large ($n-3$). One can derive this from a result of Katona and Kierstead \cite{KK} (for $n\ge 15$) but a direct inductive argument also gives it easily for any $n\ge 4$. \section{Partitions by monochromatic loose cycles} \subsection{Sketch of the proof of Theorem \ref{tetel}} \noindent\bf Proof. \rm The proof uses the {\em greedy-absorbing} technique that was developed in \cite{EGYP} and is used in most of the papers in this area. Moreover we adapt ideas of \cite{SG} to move from complete to arbitrary graphs and ideas from \cite{GYS} to move from graphs to hypergraphs. A special $k$-uniform hypergraph $T_t$, the \it crown \rm is defined as follows. Consider a $k$-uniform loose cycle (or simply a cycle) $C$ with edges $e_i$, $i=1,2,\dots, t$, the {\em base of the crown}, where $V(C)=\{x_1,\dots,x_{t(k-1)}\}$ and $e_i=\{x_i,\dots,x_{i+k-1}\}$ for $i=j(k-1)+1$, $j=0,\dots, t-1$. There are $t$ further vertices, {\em the rim of the crown} (denoted by $A$): for each $i, i=1,\dots,t$ let $v_i$ be a new vertex (not in $C$). Then we add $k$ new edges in the form $\{v_i,x_j,x_{j+1},\dots,x_{j+k-2}\}$ for all $x_j\in e_i$. Finally we add to the crown all missing $k$-sets that are consecutive on $C$. Thus a crown has $t(k-1)+t=tk$ vertices, $t(k-1)+tk$ edges and its maximum degree is $2k$. For the case $k=2$, $T_t$ is a cycle $C_t$ whose edges are extended to triangles using $t$ distinct vertices, it was called a triangle-cycle in \cite{EGYP}. The most important property of a crown $T_t$ is that after the deletion of any subset of $A$, we still have an ``almost'' Hamiltonian cycle in the remainder of $T_t$, i.e. a loose cycle containing all but at most $k-2$ vertices from the remainder of $T_t$. Following the proof technique in \cite{GYS}, we find the cycle cover in the following steps. \begin{itemize} \item Step 1: We find a sufficiently large monochromatic (say red) crown $T_t$ in $H$. \item Step 2: We remove the vertices of $T_t$ from $H$. We greedily remove a number (depending on $r$, $k$ and $\alpha$) of vertex disjoint monochromatic loose cycles from the remainder in $H$ until the number of leftover vertices is much smaller than $t$. \item Step 3: We will decompose the set of leftover vertices $B$ into two classes $B=B'\cup B''$. For $B'$, we will combine the vertices of $B'$ with some vertices of the rim $A$ of the crown $T_t$ by using the ``bipartite'' hypergraph between $B'$ and $A$. \item Step 4: We will decompose the set $B''$ into a bounded number of subsets such that the independence number of the hypergraphs induced on these sets will be smaller than $\alpha$, so we can use induction on $\alpha$ within each of these subsets. \item Step 5: Finally we find a red loose cycle that spans all but at most $k-2$ of the remaining vertices of $T_t$. \end{itemize} The organization of the paper follows this outline, after some tools from Ramsey Theory we discuss each step one by one. Since probably our bound is far from best possible anyway, we make no attempt at computing the constant $c(r,k,\alpha)$. It would be desirable to improve on this bound. \subsection{The main tool from Ramsey Theory} For $k$-uniform hypergraphs $H_1, \ldots , H_r$, the Ramsey number $R(H_1,\ldots , H_r)$ is the smallest positive integer $N$ such that, in any $r$-coloring of the edges of the complete $k$-uniform hypergraph $K^k_N$ with colors $1, \ldots , r$, there is a monochromatic copy of $H_i$ in color $i$ for some $i, 1\leq i \leq r$. A central tool in our proof will be the linearity of Ramsey numbers of hypergraphs with bounded degree, see \cite{CFS} and also \cite{I}, \cite{NORS}, \cite{CFKO}, \cite{CFKO2}. We will use this theorem in the following form. \begin{lemma}\pont\label{ramsey} If $H_1, \ldots , H_r$ are k-uniform hypergraphs each with $n$ vertices and maximum degree $\Delta$ and $\alpha$ is a positive integer, then $$R(H_1, \ldots , H_r, K_{\alpha+1}) \leq c(r, k, \Delta, \alpha)n.$$ \end{lemma} Indeed, in our hypergraph $H$ we will think of the missing edges as edges in the last color. Then since the independence number is $\alpha$ in $H$, we have no $K_{\alpha+1}$ in the last color, so we must have a $H_i$ in color $i$ for some $1\leq i \leq r$. Lemma \ref{ramsey} follows immediately from the following. \begin{lemma}[Conlon, Fox, Sudakov, Theorem 5 in \cite{CFS}]\pont\label{ramsey1} If $H_1, \ldots , H_r$ are k-uniform hypergraphs each with $n$ vertices and maximum degree $\Delta$, then $$R(H_1, \ldots , H_r) \leq c(r, k, \Delta)n.$$ \end{lemma} \subsection{Proof of Theorem \ref{tetel}} \subsubsection{Step 1} We are given an $r$-coloring of the edges of a $k$-uniform hypergraph $H$ on $n$ vertices with independence number $\alpha(H)=\alpha$. We may assume that $n$ is sufficiently large in terms of $r, k$ and $\alpha$. Consider the crown $T_t$ defined above. We will need the following important property of crowns. \begin{lemma}[Lemma 1 in \cite{GYS}]\pont\label{crown} Suppose that $T_t'$ 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 $T_t'$ can be partitioned into a loose cycle and at most $k-2$ vertices. \end{lemma} Since the crown has maximum degree $2k$, by Lemma \ref{ramsey}, there is a suitable function $f(r,k,\alpha)$ such that in our $H$ there is a monochromatic (say red) crown $T_t$ with $t\geq n/f(r,k,\alpha)$. Indeed, apply Lemma \ref{ramsey} with $H_1= \ldots =H_r=T_t$ and $$t=\lfloor \frac{n}{kc(r, k, 2k, \alpha)}\rfloor,$$ where $c(r, k, \Delta, \alpha)$ is the coefficient in Lemma \ref{ramsey}. Lemma \ref{ramsey} implies that there is a monochromatic (say red) crown $T_t$ and thus $f(r,k,\alpha)=2kc(r, k, 2k, \alpha)$ can be chosen. Denote the rim of this red crown by $A$. \subsubsection{Step 2} Set $R=V(H)\setminus V(T_t)$ and find consecutively monochromatic vertex disjoint loose cycles in $R$, at each step selecting a largest possible one. There is always one which covers at least a $1/f(r,k,\alpha)$-fraction of the vertices in the remaining uncovered part, because a loose cycle has maximum degree two. (There is a better bound, however, for easier computation we just use $f(r,k,\alpha)$ at each step.) After $s$ steps we are left with an uncovered subset $B$. We wish to choose $s$ such that for the remaining set $B$ of vertices we get $$|B|\leq \frac{1}{r^9\alpha^{9(k-1)}} \frac{n}{f(r,k,\alpha)}\leq \frac{t}{r^9\alpha^{9(k-1)}}.$$ Since after $s$ steps at most $$(n-|V(T_t)|)\left(1 - \frac{1}{f(r,k,\alpha)}\right)^s$$ vertices are left uncovered, we have to choose $s$ to satisfy $$(n-|V(T_t)|)\left(1 - \frac{1}{f(r,k,\alpha)}\right)^s \leq \frac{1}{r^9\alpha^{9(k-1)}} \frac{n}{f(r,k,\alpha)}.$$ This inequality is certainly true if $$\left(1 - \frac{1}{f(r,k,\alpha)}\right)^s \leq \frac{1}{r^9\alpha^{9(k-1)}f(r,k,\alpha)},$$ which in turn is true using $1-x\leq e^{-x}$ if $$e^{-\frac{s}{f(r,k,\alpha)}} \leq \frac{1}{r^9\alpha^{9(k-1)}f(r,k,\alpha)}.$$ This shows that we can choose $s = \lceil f(r,k,\alpha) \log (r^9\alpha^{9(k-1)}f(r,k,\alpha)) \rceil$. \subsubsection{Step 3} In this step we will find the decomposition of the set of remaining vertices $B=B'\cup B''$. For this purpose first we will define an auxiliary hypergraph. Given a $(k-1)$-element subset $S$ denote by $N_A(S)$ the {\em neighborhood} of the set $S$ in $A$ (recall that $A$ was the rim of the crown), i.e. the set of those vertices of $A$ that form an edge of our hypergraph $H$ together with $S$; $N_A^c(S)$ denotes the neighborhood in color $c$. The auxiliary $(k-1)$-uniform hypergraph $H_1$ is constructed on the vertex set $B$ and a $(k-1)$-element subset $S$ is put in $E(H_1)$ if $$|N_A(S)|\geq \frac{t}{\alpha^{k-1}}.$$ Furthermore, the color of the edge $S$ will be a majority color $c$ of these edges, so we have $$|N_A^c(S)|\geq \frac{t}{r\alpha^{k-1}} .$$ In $H_1$ we call two edges a {\em good pair} if they intersect in exactly one vertex and have the same color in $H_1$. In $H_1$ we consider a maximum set of pairwise disjoint good pairs with the following property: \begin{enumerate} \item For any good pair $S_1,S_2$ of color $c$ in our collection $$|N_A^c(S_1)\cap N_A^c(S_2)| \geq \frac{t}{r^3\alpha^{3(k-1)}} .$$ \end{enumerate} Then $B'$ is defined as the set of vertices covered by these good pairs and set $B''=B\setminus B'$. Consider the set of good pairs in $B'$ colored with color $c$ for some $c$. Next we define an auxiliary graph $G_1^c$. The vertices correspond to the good pairs of color $c$ and we put an edge between two vertices corresponding to good pairs $(S_1,S_2)$ and $(S_1',S_2')$ if \beq\label{sok}|N_A^c(S_1)\cap N_A^c(S_2)\cap N_A^c(S_1')\cap N_A^c(S_2')| \geq \frac{t}{r^9\alpha^{9(k-1)}}.\eeq Then we have the following claim for $G_1^c$. \begin{claim}\pont\label{alpha} $\alpha(G_1^c) \leq r^3 \alpha^{3(k-1)}$. \end{claim} Indeed, putting $l=r^3 \alpha^{3(k-1)}$ assume indirectly that $x_1, x_2, \ldots , x_l, x_{l+1}$ are pairwise non-adjacent vertices in $G_1^c$. If $x_i$ corresponds to the good pair $(S_1^i,S_2^i)$, set $$N_i^c= N_A^c(S_1^i)\cap N_A^c(S_2^i).$$ By definition, $|N_i^c|\geq \frac{t}{l} $ for any $i$, $1\leq i \leq l+1$. Therefore, $$|A|=t \geq |\cup_{i=1}^{l+1} N_i^c| \geq (l+1) \frac{t}{l} - \sum_{1\leq i< j\leq l+1} |N_i^c\cap N_j^c|\geq$$ $$\geq t \left( 1+ \frac{1}{l} - {l+1\choose 2}/l^3\right) > t,$$ a contradiction proving the claim. By a theorem of P\'osa \cite{POS} (see also Exercise 8.3 in \cite{LO}) the vertices of $G_1^c$ can be covered by not more than $\alpha(G_1^c)\leq l=r^3 \alpha^{3(k-1)}$ vertex disjoint cycles, edges and vertices. We will show that we can ``lift" these cycles up into loose cycles of $H$ that will cover the same vertices in $B'$ and some more vertices from $A$. To achieve this, each edge of the cycle between good pairs $(S_1,S_2)$ and $(S_1',S_2')$ will be extended greedily by a vertex $v$ from $A$ that forms an edge with {\em all} four $(k-1)$-element subsets $S_1, S_2, S_1'$ and $S_2'$. From (\ref{sok}) it follows that we can always find a vertex of $A$ that was not used on any of the previous extensions since $$|V(G^c)|\leq |B| \leq \frac{t}{r^9\alpha^{9(k-1)}}.$$ Then indeed we can form a loose cycle using these extensions. Say we have two consecutive edges $e$ and $e'$ on a cycle, where $e$ is between the good pairs $(S_1,S_2)$ and $(S_1',S_2')$, and $e'$ is between the good pairs $(S_1',S_2')$ and $(S_1'',S_2'')$ and assume that $e$ was extended by $v$ and $e'$ was extended by $v'$. Then the loose cycle contains edges $$(S_2,v), (v,S_1'), (S_2',v'), (v',S_1''), \ldots$$ and it continues in this fashion until it is closed into a loose cycle. From the construction this is indeed a loose cycle. \subsubsection{Step 4} Here we deal with the set $B''$. The key to this step is the following claim. \begin{claim}\label{B''}\pont Let $I$ be an independent subset of the auxiliary hypergraph $H_1$. Then if we restrict our original hypergraph $H$ to $I$, the independence number decreases, i.e. $\alpha(H|_{I})\leq \alpha -1$. \end{claim} Indeed, otherwise let us take an independent set $\{b_1, b_2, \ldots , b_{\alpha }\}$ in $H|_{I}$. Since $I$ is an independent set in $H_1$, for any $(k-1)$-element subset $S\subseteq \{b_1, b_2, \ldots , b_{\alpha }\}$ we have $$|N_A(S)|< \frac{t}{\alpha^{k-1}}.$$ But we have ${\alpha \choose k-1}\leq \alpha^{k-1}$ such $(k-1)$-element subsets $S$ in $\{b_1, b_2, \ldots , b_{\alpha }\}$, and thus we can choose a vertex $a\in A$ that does not form an edge with any of the subsets $S$, giving an independent set of size $\alpha +1$ in $H$, a contradiction. But then, we can iterate our whole procedure within an independent set of $H_1$. Thus our goal is to partition $B''$ into sets that are independent in $H_1$. For this purpose we use the fact that the cover with good pairs was maximum, so in $B''$ we cannot select any good pair with the given property. We call a set of $m$ edges in $H_1|_{B''}$ an $m$-{\em sunflower}, if they all intersect in $v$ but no two of them intersect at any vertex different from $v$. \begin{claim}\label{sunflower}\pont In $H_1|_{B''}$ we cannot have an $m$-sunflower with $m=r^2\alpha^{k-1} + 1$. \end{claim} Indeed, otherwise consider an $m$-sunflower with $m=r^2 \alpha^{k-1} + 1$ and take the subset $m'$-sunflower with a majority color (say color $c$), so $m'> r \alpha^{k-1}$. Then we will show that two of the edges will form a good pair with the required property, contradicting the fact that we had a maximum set of good pairs. Define the auxiliary graph $G_2^c$ where the vertices correspond to the $m'$ edges of the sunflower and we put an edge between edges $S_1$ and $S_2$ if they form a good pair with $$|N_A^c(S_1)\cap N_A^c(S_2)| \geq \frac{t}{r^3\alpha^{3(k-1)}}.$$ Similarly to Claim \ref{alpha} we can show that $$\alpha (G_2^c) \leq r \alpha^{k-1}.$$ Thus on a set of $m'(> r \alpha^{k-1})$ vertices we must have an edge, giving indeed a good pair and the required contradiction. Finally we will need the following. For a hypergraph $H$, the {\em chromatic number} of $H$ is the least number of colors needed to color the vertices, so that there is no monochromatic edge (sometimes this is called the {\em weak chromatic number}). \begin{claim}\label{uresek}\pont If in a hypergraph $H$ there is no $m$-sunflower then the chromatic number of $H$ is at most $m$. \end{claim} One can easily prove the claim by coloring the vertices with the greedy algorithm, assigning at each step the smallest color that does not create monochromatic edges. The appearance of color $m+1$ would clearly create an $m$-sunflower thus the algorithm properly colors with at most $m$ colors. (Note that for $m=2$ this claim is Exercise 13.33 in \cite{LO}.) Then Claims \ref{sunflower} and \ref{uresek} imply that the chromatic number of $H_1|_{B''}$ is at most $m=r^2\alpha^{k-1} + 1$ and thus we can partition $B''$ into at most $m=r^2\alpha^{k-1} + 1$ independent sets, as desired. Hence as mentioned above we can iterate the whole process within these independent sets. \subsubsection{Step 5} After removing the vertex disjoint monochromatic loose cycles covering $B'$ by Lemma \ref{crown} we still have a red cycle in the remainder of the triangle cycle $T_t$ that covers all but at most $k-2$ vertices. Thus, if $g(r,k,\alpha)$ is our bound on the total number of vertex disjoint monochromatic cycles we used in the partition, we get the following recursion in $\alpha$, $$g(r,k,\alpha) \leq $$ $$ \lceil f(r,k,\alpha) \log (r^9\alpha^{9(k-1)}f(r,k,\alpha)) \rceil + r^4 \alpha^{3(k-1)} + 1 + (k-2)+ (r^2\alpha^{k-1} + 1)g(r,k,\alpha -1).$$ Repeating this for all $k-2