Rainbow spanning structures in graph and hypergraph systems

Abstract

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 $\text{G}=\{G_1,G_2,\dots ,G_m\}$ 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 $\phi :E(H)\to [m]$ such that $e\in E(G_{\phi (e)})$ for each $e\in E(H)$. Note that if $|E(H)|=m$, then $\phi$ is a bijection and thus $H$ contains exactly one edge from each $G_i$. 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\mid n$ and $\delta (G_i)\ge (1-\frac{1}{t}+\epsilon )n$ for each $i\in [\frac{n}{t}(\genfrac{}{}{0ex}{}{t}{2})]$, then $\text{G}$ contains a rainbow $K_t$-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\in [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.

To appear in Forum of Mathematics, Sigma

References in corpus (3)

• On a rainbow version of Dirac's theorem
• A better bound on the size of rainbow matchings
• Rainbow Pancyclicity in Graph Systems

Cited by in corpus (1)

• Transversal Hamilton cycle in hypergraph systems