Rainbow spanning structures in graph and hypergraph systems

Yangyang Cheng ; Jie Han ; Bin Wang ; Guanghui Wang

Forum of Mathematics, Sigma, Tome 11 (2023)

Résumé

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 $\mathit {\mathbf {G}}=\{G_1, G_2,\ldots , 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 $\varphi : E(H)\rightarrow [m]$, such that $e\in E(G_{\varphi (e)})$ for each $e\in E(H)$. Note that if $|E(H)|=m$, then $\varphi $ 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)\geq (1-\frac {1}{t}+\varepsilon )n$ for each $i\in [\frac {n}{t}\binom {t}{2}]$, then $\mathit {\mathbf {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 problem, which reduces it to subproblems with finitely many colors.

Détail

DOI : 10.1017/fms.2023.92