% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P2.33}{21(2)}{2014} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \def\qed{\ifhmode\unskip\nobreak\fi\quad\ifmmode\Box\else$\Box$\fi} %\linespread{1.3} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf A note on covering\\ edge colored hypergraphs\\ by monochromatic components} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Shinya Fujita\thanks{Supported by the Japan Society for the Promotion of Science Grant-in-Aid for Young Scientists (B) (20740095).}\\ \small International College of Arts and Sciences\\[-0.8ex] %\small Solatido College\\[-0.8ex] \small Yokohama City University\\[-0.8ex] \small 22-2, Seto, Kanazawa-ku\\[-0.8ex] \small Yokohama, 236-0027, Japan\\ \small\tt shinya.fujita.ph.d@gmail.com\\ \and Michitaka Furuya \\ \small Dept. of Mathematical Information Science \\[-0.8ex] \small Tokyo University of Science\\[-0.8ex] \small 1-3 Kagurazaka, Sinjuku-ku\\[-0.8ex] \small Tokyo 162-8601, Japan\\ \small\tt michitaka.furuya@gmail.com\\ \and Andr\'as Gy\'arf\'as\thanks{Supported by the Hungarian Foundation for Scientific Research Grant (OTKA) No. K104343.} \qquad \'Agnes T\'oth\thanks{Supported by the Hungarian Foundation for Scientific Research Grant (OTKA) Nos. K104343, K108947.}\\ \small Alfr\'ed R\'enyi Intitute of Mathematics\\[-0.8ex] \small Hungarian Academy of Sciences\\[-0.8ex] \small 1364 Budapest, P.O. Box 127, Hungary \\ \small\tt \{gyarfas.andras, toth.agnes\}@renyi.mta.hu } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Feb 22, 2014}{Mar 31, 2014}{May 13, 2014}\\ \small Mathematics Subject Classifications: 05C15, 05C70} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} For $r\geq 2$, $\alpha \geq r-1$ and $k\geq 1$, let $c(r,\alpha ,k)$ be the smallest integer $c$ such that the vertex set of any non-trivial $r$-uniform $k$-edge-colored hypergraph ${\cal H}$ with $\alpha ({\cal H})=\alpha$ can be covered by $c$ monochromatic connected components. Here $\alpha({\cal{H}})$ is the maximum cardinality of a subset $A$ of vertices in $\cal{H}$ such that $A$ does not contain any edges. An old conjecture of Ryser is equivalent to $c(2,\alpha,k)=\alpha (r-1)$ and a recent result of Z. Kir\'aly states that $c(r,r-1,k)=\lceil \frac{k}{r}\rceil$ for any $r\ge 3$. Here we make the first step to treat non-complete hypergraphs, showing that $c(r,r,r)=2$ for $r\ge 2$ and $c(r,r,r+1)=3$ for $r\ge 3$. % keywords are optional % \bigskip\noindent \textbf{Keywords:} graph reconstruction %conjecture; Broglington manifold; Pipletti's classification \end{abstract} \bigskip \section{Introduction and results} A conjecture generally attributed to Ryser (appeared in his student, Henderson's thesis, \cite{HE}) states that for $k$-uniform $k$-partite hypergraphs $\tau\le (k-1)\nu$. Here $\tau$ denotes the minimum number of vertices which covers all the edges, and $\nu$ is the maximum number of disjoint edges in the hypergraph. A $k$-uniform hypergraph is \emph{$k$-partite} if the vertices can be paritioned into $k$ disjoint sets such that every edge meets all of them. The following equivalent formulation is from \cite{EGYP, Gy}. \begin{conjecture}\label{rys} In every $k$-coloring of the edges of a graph $G$, the vertex set of $G$ can be covered by the vertices of at most $\alpha(G)(k-1)$ monochromatic connected components. \end{conjecture} For $k=2$ Conjecture \ref{rys} is equivalent to K\"onig theorem \cite{Ko} and the case $k=3$ is solved by a celebrated theorem of Aharoni using new and significant ideas \cite{A}. In the special case when $\alpha(G)=1$, i.e. for complete graphs, the cases $k=3,4$ are solved in \cite{Gy} and \cite{DU}, and the case $k=5$ in \cite{DU} and \cite{TU}. Thus we know the following results. \begin{theorem}\label{graphcov} Let $k\in\{2,3\}$. Then the vertex set of any $k$-edge-colored graph $G$ can be covered by $(k-1)\alpha (G)$ monochromatic connected components, and this bound is sharp. %That is, $c(2,\alpha,k)=(k-1)\alpha$. \end{theorem} \begin{theorem}\label{compgraphcov} Let $k\in\{2,3,4,5\}$. Then the vertex set of any $k$-edge-colored complete graph can be covered by $k-1$ monochromatic connected components, and this bound is sharp. %That is, $c(2,1,k)=k-1$. \end{theorem} The third author initiated the study of the analogue of Ryser's conjecture for $r$-uniform hypergraphs and the following result of Z. Kir\'aly \cite{Ki} answered completely the case of complete $r$-uniform hypergraphs. Connected components of hypergraphs are defined as the connected components of the graph defined by the pairs of vertices that are covered by some edge of the hypergraph. One-vertex components are called trivial components. \begin{theorem}\label{comphypcov} Let $r\geq 3$. If the edges of a complete $r$-uniform hypergraph ${\cal H}$ are $k$-colored then $V({\cal H})$ can be covered by $\lceil k/r \rceil$ monochromatic connected components, and this bound is sharp. %That is, $c(r,r-1,k)=\lceil k/r \rceil$. \end{theorem} The special case $k=r$ of Theorem \ref{comphypcov} was known before \cite{Gy}. In this note we make the first step to move from complete hypergraphs to general ones. A subset of vertices in a hypergraph is {\em independent} if it does not contain any edge of the hypergraph. The maximum number of independent vertices in a hypergraph ${\cal H}$ is denoted by $\alpha({\cal H})$. For an edge-colored hypergraph ${\cal H}$, let $c({\cal H})$ be the minimal $c$ such that $V({\cal H})$ can be covered by the vertices of $c$~monochromatic components. For $r\geq 2$, $\alpha \geq r-1$ and $k\geq 1$, let $c(r,\alpha ,k)$ be the smallest integer $c$ such that $c({\cal H})\leq c$ for all non-trivial $r$-uniform $k$-edge-colored hypergraph ${\cal H}$ with $\alpha ({\cal H})=\alpha$. The hypergraph is called \emph{non-trivial} if it has at least one edge. Our main result is the following theorem. \begin{theorem}\label{rrr} Let $r\ge 2$. Let ${\cal H}$ be an $r$-uniform hypergraph with $\alpha({\cal H}) = r$, $|V({\cal H})|>r$, and its edges are colored with $k\le r$ colors. Then $V({\cal H})$ can be covered by at most two monochromatic components. That is, $c(r,r,r)\le 2$. \end{theorem} The bound in Theorem \ref{rrr} is sharp, $c(r,r,r)\ge 2$. A trivial example is the complete $r$-uniform hypergraph plus one isolated vertex. Color its edges with $r$ colors arbitrarily. This ${\cal H}$ satisfies $\alpha ({\cal H})=r$ and one needs two monochromatic components to cover all vertices because ${\cal H}$ is not connected. Another example is the following. Set $V=\{1,2,\dots ,r+2\}$, and let $E({\cal H})$ be all the $r$-sized subsets of $V$ except $\{1,2,\dots ,r\}$, and color the edge $E$ with the smallest element of $V\setminus E$ (this is at most $r$). It is easy to check that $\alpha ({\cal H})=r$, and it cannot be covered by one monochromatic connected component, because for any $i\in \{1,2,\dots ,r\}$ the vertex $i$ is not covered by any edge in color $i$. %(Consider the graph $G$ on the vertex set $V$ with edge set $E(G)=\{V\setminus e\ :\ e\in E({\cal H})\}$, and color the edge $V\setminus e$ with the color of $e$. Observe that the properties of ${\cal H}$ can be expressed with the properties of $G$ as follows. We have $\alpha({\cal H})=r$ iff there is no isolated vertex in $G$. There is no monochromatic component which covers the whole vertex set of ${\cal H}$ iff each monochromatic component of $G$ is a star.)\\ A less trivial example is the $r$-uniform hypergraph with vertices partitioned into $r$ classes and having all edges that do not meet all classes. The color of an edge $E$ is the smallest index $i$ for which $E$ does not meet class $i$. For this hypergraph $\cal{H}$, $\alpha({\cal{H}})=r$ and one monochromatic component does not cover its vertices. The theorem is also sharp in another sense, namely $c(r,r+1,r)>2$ and $c(r,r,r+1)>2$. The first is shown by the example of a complete $r$-uniform hypergraph and two isolated vertices with an arbitrary coloring of the edges. To see the second inequality, take a complete $r$-uniform hypergraph on $r+1$ vertices whose $r+1$ edges colored with different colors and add one isolated vertex. Our second result makes one more step (we do not have a reasonable conjecture for $c(r,\alpha,k)$ in general). \begin{theorem}\label{rrrplus1} Let $r\ge 3$ and ${\cal H}$ be an $r$-uniform hypergraph with $\alpha({\cal H}) = r$, $|V({\cal H})|>r$, and its edges are colored with $k\le r+1$ colors. Then $V({\cal H})$ can be covered by at most three monochromatic components. That is, $c(r,r,r+1)\le 3$. \end{theorem} For $r=2$ Theorem \ref{rrrplus1} is not true, $c(2,2,3)=4$, in fact $c(2,\alpha,3)=2\alpha$ follows from the result of Aharoni \cite{A}. To see that Theorem \ref{rrrplus1} is sharp, partition $V$ into $r+2$ nonempty sets $A_i$, $|A_{r+2}|=1$. The edges are defined as $r$-element subsets $T\subset V$ not covering $A_{r+2}$ and the color of $T$ is defined as the smallest $i$ such that $A_i\cap T=\emptyset$. Since each independent set must contain the vertex in $A_{r+2}$, the independence number of this hypergraph is $r$ and it is immediate that two monochromatic components cannot cover $V$. We present the proof of Theorem \ref{rrrplus1} first (although it uses Theorem \ref{rrr} for $r=3$) because its proof is easier. \section{Proof of Theorem \ref{rrrplus1}} Let $\cal{H}$ be a non-trivial $r$-uniform $(r+1)$-edge-colored hypergraph with $\alpha({\cal H})=r$. We distinguish two cases. \noindent {\bf Case 1: $r=3$.} If each edge $E$ of $\cal{H}$ in color $1$ is covered by a monochromatic component of some color $c(E)$ different from $1$ then we can recolor all edges $E$ of color $1$ with $c(E)$ and let $\cal{H}'$ be the resulting hypergraph. By Theorem \ref{rrr}, we can cover $\cal{H}'$ with $c(3,3,3)=2$ monochromatic components. Then we can find the corresponding two monochromatic components in $\cal{H}$ and they cover $V(\cal{H})$, as desired. Thus we may assume that there is an edge $E$ in color $1$, such that $E$ is not covered by any component of color different from $1$. For each $2$-element subset $Y$ of $E$, let $C_Y$ be the set of colors $i$ for which there exists a monochromatic connected component of color $i$ which contains $Y$. Since $E$ has color $1$, $1\in C_Y$ for every $Y\subset E$. Note that for two different $2$-element subsets $Y_1,Y_2\subset E$, $(C_{Y_1}\cap C_{Y_2})-\{1\}=\emptyset$ by the definition of $E$. Hence, using that $\cal H$ is $4$-edge-colored one can easily see that there is a $Y_0\subset E$, $|Y_0|=2$ with $|C_{Y_0}|\le 2$. Let $H_1$ be the component of color $1$ containing $E$ and $H_2$ be the component containing $Y_0$ in the color of $C_{Y_0}$ different from $1$, say $2$. In the case where $C_{Y_0}=\{1\}$, let $H_2$ be empty. Set $Z=V({\cal H})-(V(H_1)\cup V(H_2))$. Observe that for any two vertices $z_1,z_2\in Z$, the triples $Y_0\cup z_1,Y_0\cup z_2$ cannot be edges of ${\cal H}$ from the definition of $Y_0$ and $Z$. Thus, in the quadruple $Y_0,z_1,z_2$ one of the triples containing both $z_1,z_2$ must be edges of ${\cal H}$, because $\alpha({\cal H})=3$. This induces a coloring on the complete graph with vertex set $Z$, with $2$ colors (colors $3,4$) if $H_2$ is nonempty, or with $3$ colors (colors $2,3,4$) if $H_2$ is empty. Using Theorem \ref{compgraphcov}, $Z$ can be covered by the vertices of one (if $H_2$ is nonempty) or two monochromatic connected components and they are obviously subsets of components in the same color in ${\cal H}$ as well. Together with $H_1,H_2$ (if $H_2$ is nonempty) or with $H_1$ (if $H_2$ is empty) we have the required cover with three monochromatic components. \noindent {\bf Case 2: $r>3$.} Set $t=\lceil \frac{r}{2} \rceil$. If there is a $t$-element set $S$ that is not covered by any monochromatic component, consider $T\subset V-S$ such that $|T|=r+1-t$. From the assumption of the theorem, the set $S\cup T$ must contain an edge $E\in {\cal{H}}$ and since $S$ is not covered by $E$ from the choice of $S$, $T\subset E$. Thus we may color the complete hypergraph ${\cal{H}^*}$ on the $(r+1-t)$-element subsets of $V-S$ by the color of $E$. Since $r+1-t=r+1-\lceil \frac{r}{2}\rceil \ge 3$ for $r\ge 4$, we can apply Theorem \ref{comphypcov} to ${\cal{H}^*}$. Observing that $ 2(r+1-t)\ge r+1$, ${\cal{H}^*}$ can be covered by two connected monochromatic components and (since the $r$-sets defining the colors cover $S$ apart from possibly one vertex) these two components must cover $S$ also, apart from at most one vertex. Thus, adding the possibly non-covered vertex as a trivial component, we have the required cover with three components. If all $t$-element subsets $S$ of vertices of $\cal{H}$ are covered by some monochromatic component, then we may color the complete hypergraph ${\cal{H}^{**}}$ of the $t$-sets $\cal{H}$ with $r+1$ colors. For $r\ge 5$ we have $t=\lceil \frac{r}{2} \rceil\ge 3$ and can apply Theorem \ref{comphypcov} again and, since $3t=3\lceil \frac{r}{2} \rceil\ge r+1$ we can cover ${\cal{H}^{**}}$ with at most three components, and this obviously induces the required cover for $\cal{H}$. The only remaining case is when $r=4$ and every pair of vertices is covered by a monochromatic component. First suppose that there is a pair of vertices $x,y$ contained in just one monochromatic component $C_1$. Then we color every triple $T$ in $Z=V({\cal{H}})\setminus C_1$ with the color of the edge of $\cal{H}$ in $T\cup \{x,y\}$ containing $T$ and one of $x,y$. The used color must be different from the color of $C_1$ therefore the obtained complete $3$-uniform hypergraph will be colored with $4$ colors. By Theorem \ref{comphypcov} it can be covered by at most two monochromatic components which expand to monochromatic components of $\cal H$, and with $C_1$ they form the required covering. Similarly, if there is a pair of vertices $x,y$ contained in exactly two monochromatic components $C_1, C_2$, then again, we color the triples of $Z=V({\cal H})\setminus (C_1\cup C_2)$ as we did before. In this case the triples could get just three colors so by Theorem \ref{comphypcov}, $Z$ can be covered by one monochromatic component, and with $C_1, C_2$ we get the required covering of $\cal H$. Note that (in both cases) if there is no triple in $Z$, that is $|Z|\le 2$, then our argument still works since we need only one monochromatic component to cover $Z$ (because every pair of vertices is covered by a monochromatic component). Finally, when every pair of vertices is contained in at least three monochromatic components, we pick an arbitrary vertex $x$ and choose three colors whose monochromatic components cover $x$. These components must cover the whole vertex set of $\cal H$ because if any vertex $z$ would be uncovered, the pair $x,z$ would be in at most two monochromatic components. \qed \section{Proof of Theorem \ref{rrr}} The statement for $r=2$ is a solved special case of Conjecture \ref{rys}. Let $r\ge 3$. We may assume that $c(\mathcal{H})\geq 2$ allowing us to \emph{define $t$ as the smallest positive integer such that there are $t$ vertices of ${\cal H}$ which are not contained in any non-trivial monochromatic component of ${\cal H}$.} We may also assume that $t\ge 2$, otherwise we would have an isolated vertex, and then the remaining at least $r$ vertices form a complete $r$-uniform hypergraph colored with $r$ colors. Then, by the case $k=r$ of Theorem \ref{comphypcov} it can be spanned by one monochromatic component. Adding the isolated vertex as a single component we have a cover with two components. In the following we consider three cases according to the value of $t$ (and $r$), and handle them separately. \subsection*{Case 1: $t\ge \max\{\frac{r}{2} +1,4\}$, or $(r,t)=(3,3)$.} \begin{proof}[Proof in case 1.] By the definition of $t$ we know that for every $(t-1)$-element subset $S$ of $V({\cal H})$ there is a monochromatic component $C_S$ containing $S$. We color any $S$ with the color of $C_S$, and obtain a complete $(t-1)$-uniform hypergraph on $V({\cal H})$, whose edges are colored with $k$ colors. This hypergraph is denoted by ${\cal H}^*$. Any monochromatic component of ${\cal H}^*$ is a subset of a monochromatic component of ${\cal H}$. When $t-1\ge 3$, we can use Theorem~\ref{comphypcov}, so ${\cal H}^*$ can be covered by at most $\lceil k/(t-1)\rceil$ monochromatic components. Also, $t\ge \frac{r}{2}+1$, this gives us a covering with $\lceil k/(t-1)\rceil \le \lceil r/(r/2 +1-1)\rceil = 2$ monochromatic components. When $t-1=2$ and $k\le r=3$, we apply Theorem~\ref{compgraphcov}, and obtain that ${\cal H}^*$ can be covered by at most $k-1\le 2$ monochromatic components. \end{proof} \subsection*{Case 2: $t=2$.} First we need some definitions and a lemma. A \emph{bipartite hypergraph} $[A,B]$ is a hypergraph whose vertex set is partitioned into nonempty sets $A,B$ and for every edge $E$, $E\cap A, E\cap B$ are both nonempty. An $r$-uniform bipartite hypergraph $[A,B]$ is \emph{complete} if its edge set is all $r$-element sets of $A\cup B$ that meet both $A,B$. An $r$-edge-coloring of a complete $r$-uniform bipartite hypergraph $[A,B]$ is \emph{special} if the following holds. One of $A,B$ is specified as the \emph{kernel} and the other contains disjoint subsets $X_i,i\in \{1,2,\dots,r\}$. For every $i$, the edges of color $i$ form only one non-trivial component, $C_i$, with vertex set $V({\cal H})\setminus X_i$. When $r=2$ we extend the definition of special as follows. We call a $2$-edge-coloring of a bipartite graph special also when $A$ and $B$ are divided into two nonempty parts $A=A_1\cup A_2$, $B=B_1\cup B_2$ and the edges between $A_i$ and $B_j$ are colored according to the parity of~$i+j$. \begin{lemma}\label{bipcol} Let ${\cal F}=[A,B]$ be a complete bipartite $r$-uniform hypergraph, and $r\ge 2$. If the edges of ${\cal F}$ are colored with $r-1$ colors then some color class spans a connected hypergraph on $V({\cal F})$. This remains true even for $r$-edge-colorings of ${\cal F}$ unless the coloring is special. \end{lemma} \begin{proof}[Proof of Lemma \ref{bipcol}] Suppose that the edges of ${\cal F}$ are colored with $r-1$ colors. We add every $r$-subsets of $A$ and $B$ to the edge set, and color them with a new color. The $r$-uniform hypergraph so obtained is complete, and its edges are colored with $r$ colors. By Theorem \ref{comphypcov} one color spans a connected component on the whole vertex set, but this cannot be in the new color. This shows that the first part of the lemma is true. Now we consider an $r$-edge-coloring of ${\cal F}$. We may assume that for any color $c$, there is a component in $c$ which is not contained by any other component. (Otherwise, the color $c$ could be eliminated, by recoloring each edge in color $c$ to the color of the component which contains them.) \begin{claim}\label{c1} Let $r\ge 3$. For any color $c$, there is just one non-trivial component in $c$, and it contains $A$~or~$B$. \end{claim} \proof{ Let $C$ be a component in color $c$ which is not contained by any other component, so assume that $\exists a\in A$, $\exists b\in B$: $a,b\notin C$. We define a complete $(r-1)$-uniform hypergraph on $C$ colored with $r-1$ colors, in the following way. For any $X\subseteq C$, $|X|=r-1$, the set $X\cup\{a\}$ or $X\cup\{b\}$ is an edge $E_X$ of ${\cal F}$, and we transfer the color of $E_X$ to $X$. By Theorem \ref{comphypcov} (using $r-1\ge 2$) this hypergraph is spanned by one monochromatic component $D$ in color $d\neq c$. But $D$ is a monochromatic component also of ${\cal F}$ which contains $C$ (and also at least one of $a$, $b$), this contradicts the choice of $C$. Therefore $C$ contains $A$ or $B$. The other components in $c$ must be in the other part of the bipartite hypergraph, and so they must be trivial. \qed} \begin{claim}\label{c2} All the non-trivial components defined in Claim \ref{c1} contain $A$ or all of them contain~$B$. \end{claim} \proof{ Let $u_i$ be any isolated vertex in color $i$, for $i=1,2,\dots ,r$. (For every color $i$ we have such a vertex, otherwise the non-trivial component in color $i$ would span a connected component on the whole vertex set.) Take the set of all $u_i$-s, and extend it to an $r$-element set if some of the $u_i$-s are equal. This set is not an edge of ${\cal F}$ because it cannot be colored by any color. Therefore all the possible $u_i$-s are in the same side of the bipartite hypergraph, proving the statement. \qed} \smallskip Suppose that $r\ge 3$ and the hypergraph cannot be covered by a single monochromatic component. We will show that the coloring is special. By Claims \ref{c1} and~\ref{c2}, every monochromatic component contains one of the parts of the bipartite hypergraph, say $A$. Moreover, we have $r$ non-trivial monochromatic components and the intersections of their complements must be disjoint in $B$, otherwise we could choose at most $r-1$ vertices from $B$ such that from the complement of each monochromatic component we picked at least one, and by adding a vertex from $A$ the formed $r$-tuple cannot be colored by any of the $r$ colors. Therefore in this case the coloring is special with exactly $r$ colors (note that the kernel is $A$). \medskip Suppose that $r=2$. Since the statement of Claim \ref{c1} holds only for $r\ge 3$, besides the structure described above, it also could happen that there is a component $C=A'\cup B'$ in color $1$ where $A'\subseteq A$, $B'\subseteq B$, and none of $A'$, $A\setminus A'$, $B'$, $B\setminus B'$ is empty. In this case the edges between $A$ and $B'$ are colored with color $2$ as well as the edges between $A'$ and $B$. The remaining edges must be colored with $1$, otherwise one component would cover the whole vertex set. Hence also in this case the coloring is special. This completes the proof of Lemma \ref{bipcol}. \end{proof} \begin{proof}[Proof in case 2] Since $t=2$, we have two vertices, $a,b$ such that $\{a,b\}$ is not covered by any monochromatic component of ${\cal H}$, but each of them is covered by some monochromatic component. Set $X=V({\cal H})\setminus\{a,b\}$.\\ Let $C$ be a maximal monochromatic component containing $a$, say in color $1$ (clearly $b\notin C$). Set $A=V(C)\cap X$, $B=X\setminus A$, we may clearly assume that $B$ is nonempty, otherwise $C$ and $\{b\}$ cover $V({\cal H})$. Let ${\cal H}^*$ be the complete $(r-1)$-uniform bipartite hypergraph $[A,B]$ on vertex set $X$. For any $S\subseteq X$ with $|S|=r-1$, the set $S\cup \{a\}$ or $S\cup \{b\}$ is an edge of ${\cal H}$, otherwise the $(r+1)$-sized set $S\cup \{a,b\}$ would be an independent set in ${\cal H}$, contradicting the assumption $\alpha({\cal H})=r$. Transfer the color of $S\cup \{a\}$ or $S\cup \{b\}$ to $S$. From the definition of $C$, the color of the the edges of ${\cal H}^*$ in the transferred coloring cannot be $1$, therefore ${\cal H}^*$ is colored with $r-1$ colors: $2,\dots,r$. Apply Lemma \ref{bipcol} to ${\cal H}^*$ (which is $(r-1)$-uniform, and $r-1\ge 2$). If some color class spans a connected component in ${\cal H}^*$ covering $A\cup B$ then clearly at least one of $\{a,b\}$ extends this component to a component of ${\cal H}$ and with the trivial component on the remaining vertex we have the required cover. Otherwise we have a special coloring of ${\cal H}^*$ with exactly $r-1$ colors ($2,\dots,r$). \medskip \noindent\textbf{Case 2.a.} First consider the case $r-1\ge 3$ when there is just one type of special structure. Observe that for every $2\le i \le r$ the non-trivial component $D_i^*$ in this special coloring is part of a component $D_i$ of ${\cal H}$. For example, $a$ or $b$ is in $D_i$ for every $i\in \{2,\dots,r\}$. In addition, edges of color $i$ inside $X$ may also contribute to the extension of $D_i^*$ to $D_i$. For convenience, we keep the notation $X_i$ used for the exceptional part in $X$, thus for each $i$, $D_i$ covers $V({\cal H})$ with the exception of $X_i$ and exactly one vertex from $\{a,b\}$. If the kernel of the special coloring is $A$ (reps. $B$) then $\cup_{i=2}^r X_i\subseteq B$ (resp. $\cup_{i=2}^r X_i\subseteq A$). Suppose that $\cup_{i=2}^r X_i\subseteq B$ (the kernel is $A$). Consider the $(r+1)$-element set $W=\{a,y,x_2,\dots,x_r\}$, where $y\in A,x_j\in X_j$. The sets $W\setminus \{a\},W\setminus \{y\}$ cannot be edges of ${\cal H}$ since any color on them would contradict the definition of $A$ or $D_i$. By the same reason, if $W\setminus \{x_j\}$ is an edge of ${\cal H}$ for some $j>1$ then its color can be only $j$. But in this case $C\subset D_j$ with a proper containment, contradicting the definition of $C$. Therefore $W$ is independent set in ${\cal H}$, contradicting $\alpha({\cal H})=r$. Suppose that $\cup_{i=2}^r X_i\subseteq A$ (the kernel is $B$). %If $a,b$ are both in some $C_i$ ($i>1$) then $r\ge 3$ implies that we can select $j$ with $11$) then $C\cup D_i$ covers $V({\cal H})$. Thus we may assume that $b$ is not covered by any $D_i$. Consider the $(r+1)$-element set $W=\{b,y,x_2,\dots,x_r\}$, where $y\in B,x_j\in X_j$. The set $W\setminus \{b\}$ cannot be an edge of ${\cal H}$ since any color on it would contradict the definition of $A$ or $D_i$. Suppose $W\setminus \{y\}$ is an edge of ${\cal H}$ and its color is $i$. %If $i=1$ then $C$ covers $b$ and with any $D_j$ we have a cover on $V({\cal H})$. Since $b\notin C$, $i>1$, but then $D_i\cup C$ cover $V({\cal H})$. Thus we may assume that $W\setminus \{y\}$ is not an edge of ${\cal H}$. However, $W\setminus \{x_j\}$ cannot be an edge of ${\cal H}$ either, because $b$ is not covered by $D_j$. Therefore $W$ is independent set in ${\cal H}$, contradicting $\alpha({\cal H})=r$. \medskip \noindent\textbf{Case 2.b.} When $r-1=2$ and the special coloring has a kernel then the same argument shows that $c({\cal H})\le 2$. In the case of the other special coloring, ${\cal H}^*$ has two non-trivial components in both colors, and these components cover $X$ in both colors. Consider the two components in ${\cal H}^*$ in color $2$. These components are either joined by one of $a,b$ then this component cover all the vertices of ${\cal H}$ but at most one of $a,b$; or one of them with $a$ and the other with $b$ cover all the vertices of ${\cal H}$. \medskip Thus we have finished the proof in Case 2. \end{proof} \subsection*{Case 3: $r\ge 4$ and $3\le t\le \frac{r}{2}+1$.} We need yet another lemma. \begin{lemma}\label{colcov} Let ${\cal F}$ be an $r$-uniform complete hypergraph with an edge-coloring. Then no matter how the color set is partitioned into at most $r$ disjoint parts, one of them must contain such colors whose non-trivial components cover the vertex set of ${\cal F}$. \end{lemma} %\noindent In particular, if the color set is partitioned into disjoint subsets with size at most $2$ then one of the parts contains at most $2$ colors whose non-trivial components cover the vertex set of ${\cal H}$. Note, that in this case we do not restrict the number of components just the number of colors used in them. \begin{proof}[Proof of Lemma \ref{colcov}] Let $S$ be the set of colors used in the coloring of ${\cal F}$, and consider its partition into disjoint $r'\le r$ subsets $S_1, S_2, \dots ,S_{r'}$. If the non-trivial components in colors belonging to $S_i$ do not cover the vertex set of ${\cal F}$ then there is a vertex $u_i$ which is not covered by any edge colored with any element of $S_i$. If it holds for every $i\in\{1,2,\dots ,r'\}$ then let $U=\{u_1,u_2,\dots ,u_{r'}\}$, and extend it to an $r$-sized set if necessary. But $U$ cannot be colored by any color, and it contradicts the definition of ${\cal F}$. Thus there must be an $i\in \{1,2,\dots ,r'\}$ such that the non-trivial components in the colors belonging to $S_i$ cover the whole vertex set of ${\cal F}$, completing the proof. \end{proof} \begin{proof}[Proof in case 3] Let $T=\{v_1,v_2,\dots ,v_t\}$ be a set of vertices not covered by any non-trivial monochromatic component of ${\cal H}$. We know by the definition of $t$ that for any $T_i=T\setminus \{v_i\}$, $1\le i\le t$, there is at least one monochromatic component covering it. For any $X\subseteq V({\cal H})$, let $s(X)$ be the set of colors $c$ for which there is a monochromatic non-trivial component in color $c$ containing $X$. It is clear that $s(T_i)\neq\emptyset$ for any $i\in\{1,2,\dots ,t\}$. For different $i$ and $j$ the color sets $s(T_i)$ and $s(T_j)$ must be disjoint, otherwise the whole $T$ would be covered by a monochromatic component, since $T_i$ and $T_j$ are intersecting (using $t\ge 3$). Set $X=V({\cal H})\setminus T$. Consider any $(r-t+1)$-element subset $S$ of $X$. Using $|S\cup T|=r+1$, $\alpha ({\cal H})\le r$ and the definition of $T$ there must be an edge $E_S=S\cup T_i$ for some $i\in\{1,2,\dots ,t\}$. Define ${\cal H}^*$ be a complete $(r-t+1)$-uniform hypergraph on $X$, and color the edge $S$ with the color of $E_S$. We shall find either one color whose non-trivial monochromatic component in ${\cal H}^*$ covers $X$ or two colors whose non-trivial monochromatic components cover the vertices of $X$ and whose components can be extended to different $(t-1)$-element subsets of $T$. This will be enough, because every monochromatic component of ${\cal H}^*$ in a fixed color can be extended to the same $(t-1)$-element subset of $T$, joining in a monochromatic component of ${\cal H}$. Let $K'$ be the union of the $t$ nonempty disjoint sets, $s(T_1),s(T_2),\dots ,s(T_t)$, and let $k'=|K'|$. We have $k'\le k\le r$, $t\le \frac{r}{2}+1$. \begin{claim}\label{c3} $K'$ can be partitioned into $r-t+1$ parts, whose sizes are at most $2$ (the empty set is also allowed) and the elements of all $2$-sized parts are in different $s(T_i)$-s. \end{claim} \proof{ We have to create at least $M=k'-(r+1-t)$ parts with size $2$. Pick one element from each $s(T_i)$, $i=1,2,\dots ,t$ and form the set $K_1$, and put the remaining ones into the set $K_2$. Construct the $2$-sized disjoint sets by taking repeatedly one element from $K_2$, and its mate from $K_1$, so that they are from different $s(T_i)$-s. When we have $M$ $2$-sized parts or $K_2$ is exhausted, we make the remaining parts arbitrarily (selecting empty or one-element sets). Since $M=k'-(r+1-t)