P000060

杨杨 程 (山东大学)

杰 韩 (罗德岛大学)

*斌 王 (山东大学)

光辉 王 (山东大学)

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 $\emph{\textbf{G}}=\{G_1, G_2,\ldots, G_{m}\}$ of not necessarily distinct graphs on the same vertex set $[n]$, a (sub)graph $H$ on $[n]$ is rainbow if $E(H)\subseteq \bigcup_{i\in [m]}E(G_i)$ and $|E(H)\cap E(G_i)|\le 1$ for $i\in[m]$. Note that if $|E(H)|=m$, then a rainbow $H$ consists of exactly one edge from each $G_i$. Our main results are on rainbow clique-factors in (hyper)graph systems with minimum degree conditions on each individual graph. In particular, \begin{enumerate} \item we obtain a rainbow analogue of an asymptotical version of the Hajnal--Szemer\'{e}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 $\emph{\textbf{G}}$ contains a rainbow $K_t$-factor; \item we prove that for $1\le d\le k-1$, essentially a minimum $d$-degree condition forcing a perfect matching in a $k$-graph also forces rainbow perfect matchings in $k$-graph systems. \end{enumerate} 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 unknown in general). For (1) we also discuss directed versions, a multipartite version, and a hypergraph extension. Finally, to establish these results, we in fact provide a general framework to attack this type of problems, which reduces it to subproblems with \emph{finitely many} colors.

Math formula preview: