Covering complete partite hypergraphs by monochromatic components

Abstract A well-known special case of a conjecture attributed to Ryser (actually appeared in the thesis of Henderson (1971)) states that k -partite intersecting hypergraphs have transversals of at most k − 1 vertices. An equivalent form of the conjecture in terms of coloring of complete graphs is formulated in Gyarfas (1977): if the edges of a complete graph K are colored with k colors then the vertex set of K can be covered by at most k − 1 sets, each forming a connected graph in some color. It turned out that the analogue of the conjecture for hypergraphs can be answered: it was proved in Kiraly (2013) that in every k -coloring of the edges of the r -uniform complete hypergraph K r ( r ≥ 3 ), the vertex set of K r can be covered by at most ⌈ k ∕ r ⌉ sets, each forming a connected hypergraph in some color. Here we investigate the analogue problem for complete r -uniform r -partite hypergraphs. An edge coloring of a hypergraph is called spanning if every vertex is incident to edges of every color used in the coloring. We propose the following analogue of Ryser’s conjecture. In every spanning ( r + t ) - coloring of the edges of a complete r -uniform r -partite hypergraph, the vertex set can be covered by at most t + 1 sets, each forming a connected hypergraph in some color . We show that the conjecture (if true) is best possible. Our main result is that the conjecture is true for 1 ≤ t ≤ r − 1 . We also prove a slightly weaker result for t ≥ r , namely that t + 2 sets, each forming a connected hypergraph in some color, are enough to cover the vertex set. To build a bridge between complete r -uniform and complete r -uniform r -partite hypergraphs, we introduce a new notion. A hypergraph is complete r -uniform ( r , l ) -partite if it has all r -sets that intersect each partite class in at most l vertices (where 1 ≤ l ≤ r ). Extending our results achieved for l = 1 , we prove that for any r ≥ 3 , 2 ≤ l ≤ r , k ≥ 1 + r − l , in every spanning k -coloring of the edges of a complete r -uniform ( r , l ) -partite hypergraph, the vertex set can be covered by at most 1 + ⌊ k − r + l − 1 l ⌋ sets, each forming a connected hypergraph in some color.