2021/05/21 by Yangyang Cheng, Jie Han, Cheng, Yangyang +5 · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2105.10219
openalex publication_date 2021/05/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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-(1)/(t)+ε)n for each i∈[(n)/(t)\binomt2], 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.