\documentclass[12pt,reqno]{article}
%\documentstyle[12pt]{article}
\usepackage{e-jc,amsmath,amsthm,amssymb}
% Originally was P2.39, for final review, then became P2.36
% when #3693 was delayed.
\specs{P2.36}{21(2)}{2014}


%\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{\bf 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, H-1364, Hungary\\
\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 01609, U.S.A.\\[-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, H-1364, Hungary \\[-0.8ex]
\small \texttt{sarkozy.gabor@renyi.mta.hu}}

\date{\dateline{Jan 28, 2014}{May 10, 2014}{May 22, 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}.\  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=\left\lfloor \frac{n}{kc(r, k, 2k, \alpha)}\right\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$,
\begin{align*}
 g(r,k,\alpha) &\leq  \left\lceil f(r,k,\alpha) \log
(r^9\alpha^{9(k-1)}f(r,k,\alpha)) \right\rceil + r^4 \alpha^{3(k-1)} + 1\\
& \hspace*{1cm} {} +
(k-2)+ (r^2\alpha^{k-1} + 1)g(r,k,\alpha -1).
\end{align*}

Repeating this for all $k-2<j<\alpha$, finally (when $j=k-1$) we get
either a trivial hypergraph with $k-1$ vertices (and no edge) or a
complete $k$-uniform hypergraph. Then, using the bound
$g(r,k,k-1)\leq c(r,k)$ from \cite{GYS} for some function $c(r,k)$,
we get the desired bound using only $r$, $k$ and $\alpha$. This
finishes the proof of Theorem 1. $\Box$


\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}, {\bf 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, Ser. B}, {\bf 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 Journal of Combinatorial Theory, Ser. B}, {\bf 98} (2008), pp.
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), pp. 263-297.


\bibitem{CFS} D. Conlon, J. Fox, B. Sudakov, Ramsey numbers of sparse hypergraphs, {\em Random Structures and Algorithms}, {\bf 35} (2009), pp. 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}, {\bf 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, Ser. B}, {\bf 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}(1)
(2011), \#P53.

\bibitem{GYS} A. Gy\'arf\'as, G.N. S\'ark\" ozy,
Monochromatic path and cycle partitions in hypergraphs, {\em
Electronic Journal of Combinatorics}, {\bf 20}(1) (2013), \#P18.

%\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), pp. 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{KK} Gy.Y. Katona, H. Kierstead, Hamiltonian chains in Hypergraphs, {\em Journal of Graph Theory}, {\bf 30} (1999), pp. 205-212.

\bibitem{LO} L. Lov\'asz, {\em Combinatorial Problems and Exercises},
2nd edition, North-Holland, 1979.

\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}, {\bf 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), pp.
205-228.

\bibitem{PO} A. Pokrovskiy, Partitioning edge-coloured complete graphs into monochromatic cycles and
paths, {\em Journal of Combinatorial Theory, Ser. B}, {\bf 106}
(2014), pp. 70-97.

\bibitem{POS} L. P\'osa, On the circuits of finite graphs, {\em MTA Mat. Kut. Int. K\"ozl.}, {\bf 8} (1963), pp. 355-361.

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

\bibitem{SG} G.N. S\'ark\"ozy,
Monochromatic cycle partitions of edge-colored graphs, {\em Journal
of Graph Theory}, {\bf 66} (2011), pp. 57-64.

%\bibitem{RRS} V. R\"odl, A. Ruci\'nski, E. Szemer\'edi, A
%Dirac-type theorem for $3$-uniform hypergraphs, {\em Combinatorics, Probability and Computing} {\bf 15} (2006), pp. 229-251.

%\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}
\subsection{Proof of Theorem \ref{sts}} Suppose $S$ is a Steiner triple system, a Berge cycle is a cyclic ordering of its points so that no three cyclically consecutive points form a triple in $S$. For $n=7$ we have the Fano plane with $(1,2,4)$ as a cyclic generator and $1,2,3,4,5,6,7,1$ is a suitable cyclic permutation. Assume that we have $n\ge 9$ points in $S$. First we construct greedily a Berge cycle $C_{n-2}$
on $n-2$ vertices as follows.  Label a triple of $S$ with labels
$1,2,4$ and another vertex with label $3$. Select the largest $k$
such that we can label the sequence of points $L=\{1,2,\dots,k\}$ so
that no three cyclically consecutive vertices form a triple in $S$.
We claim that $k\ge n-2$. Indeed, if $x_1,x_2,x_3\notin L$  then we
can select $x_i$ such that none of the triples
$(k-1,k,x_i),(k,x_i,1)$ are in $S$ and the sequence
$\{1,2,\dots,k,x_i\}$ would be a longer sequence with the required
property. Thus we can define the point with label $n-2$ and since
there are there are no cyclically consecutive triples of $S$ in $L$,
$L$ defines a Berge cycle $C_{n-2}$ as required.

Let $x,y$ denote the two points not covered by $C_{n-2}$ and call
two cyclically consecutive pairs of points $u,v$ {\em edges} of
$C_{n-2}$ and their type $x,y,*$ is defined according to the
following three (mutually exclusive) possibilities: $(x,u,v)\in S,
(y,u,v)\in S$, neither is in $S$.

\noindent {\bf Case 1. There are three consecutive type $*$ edges,
say $(1,2),(2,3),(3,4)$.} Here we can define a Berge cycle $C_{n-1}$
by the cyclic ordering obtained from the cyclic ordering of
$C_{n-2}$ by inserting $x$ (or $y$) between $2,3$.

\noindent {\bf Case 2. There are five cyclically consecutive vertices, say
$2,3,4,5,6$ such that  neither $(2,3)$ nor $(5,6)$ is type $*$.}
Suppose w.l.o.g. that $(2,3)$ is of type $x$. Then we can define a Berge
cycle $C_{n-1}$ by the cyclic order
$$1,2,x,4,3,5,6,\dots,n-1,n-2,1.$$
Indeed, the consecutive triples $(1,2,x),(2,x,4),(x,4,3)$ are not in
$S$ because $(2,3,x)\in S$,$(4,3,5)\notin S$ because it was
consecutive in $C_{n-2}$, and $(3,5,6)\notin S$ since either
$(x,5,6)$ or $(y,5,6)\in S$.

We claim that one of the cases must indeed occur, thus we always
have a Berge cycle $C_{n-1}$. Indeed, if $C_{n-2}$ has three
consecutive type $*$ edges, case 1 occurs. Suppose $C_{n-2}$ has two
consecutive type $*$ edges, say $(i,i+1),(i+1,i+2)$. Then
$(i-1,i),(i+2,i+3)$ both have type $x$ or $y$ and this is case 2.
Thus, for every type $*$ edge $(i,i+1)$, the edges $(i-1,i),(i+1,i+2)$
are not of type $*$ and both must be continued by type $*$
edges. We conclude that type $*$ and not type $*$ edges must
alternate and this is impossible since $n$ is odd. This proves the
claim.

Our last step is to construct a Berge cycle $C_n$ from $C_{n-1}$. In
fact we can repeat the procedure: the proof works in the same way,
except if the cycle $C_{n-1}$ alternates type $*$ and not type $*$
edges. In this case suppose we have  an alternating $C_{n-1}$
starting with type $*$ edge $(1,2)$. Then we define the cyclic order
(with $x\notin C_{n-1}$) as follows: start with $1,2,x,4,3,5$ and if
$(3,5,6)\notin S$ then continue with $6,7,8,\dots,n-1,1$; if
$(3,5,6)\in S$ then $(3,5,7)\notin S$ and continue with
$7,6,8,9,\dots,n-1,1$. \qed
