Rainbow spanning structures in graph and hypergraph systems.

We study the following rainbow version of subgraph containment problems in a family of (hyper)graphs, which generalizes the classical subgraph containment problems in a single host graph. For a collection G={G1,G2,...,Gm} of not necessarily distinct k-graphs on the same vertex set [n], a (sub)graph H on [n] is rainbow if there exists an injection φ:E(H)→[m] such that e∈E(Gφ(e)) for each e∈E(H). Note that if |E(H)|=m, then φ is a bijection and thus H contains exactly one edge from each Gi. Our main results focus on rainbow clique-factors in (hyper)graph systems with minimum d-degree conditions. Specifically, we establish the following: (1) A rainbow analogue of an asymptotical version of the Hajnal--Szemerédi theorem, namely, if t∣n and δ(Gi)≥(1-1t+ε)n for each i∈[nt(t2)], then G contains a rainbow Kt-factor; (2) Essentially a minimum d-degree condition forcing a perfect matching in a k-graph also forces rainbow perfect matchings in k-graph systems for d∈[k-1]. The degree assumptions in both results are asymptotically best possible (although the minimum d-degree condition forcing a perfect matching in a k-graph is in general unknown). For (1) we also discuss two directed versions and a multipartite version. Finally, to establish these results, we in fact provide a general framework to attack this type of problems, which reduces it to subproblems with finitely many colors. [ABSTRACT FROM AUTHOR]