Rainbow spanning structures in graph and hypergraph systems


Abstract in English

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 $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_{iin [m]}E(G_i)$ and $|E(H)cap E(G_i)|le 1$ for $iin[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 $d$-degree conditions. In particular, (1) we obtain a rainbow analogue of an asymptotical version of the Hajnal--Szemer{e}di theorem, namely, if $tmid n$ and $delta(G_i)geq(1-frac{1}{t}+varepsilon)n$ for each $iin[frac{n}{t}binom{t}{2}]$, then $textbf{G}$ contains a rainbow $K_t$-factor; (2) we prove that for $1le dle 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. 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 direct

Download