A general approach to transversal versions of Dirac-type theorems

Abstract

Given a collection of hypergraphs 𝐇=(𝐻1,...,𝐻𝑚) with the same vertex set, an 𝑚-edge graph 𝐹⊂∪𝑖∈[𝑚]𝐻𝑖 is atransversal if there is a bijection 𝜙∶𝐸(𝐹)→[𝑚] such that 𝑒∈𝐸(𝐻𝜙(𝑒)) for each 𝑒∈𝐸(𝐹). How large does the minimum degree of each 𝐻𝑖 need to be so that 𝐇 necessarily contains a copy of 𝐹 that is a transversal? Each 𝐻𝑖 in the collection could be the same hypergraph,hence the minimum degree of each 𝐻𝑖 needs to be large enough to ensure that 𝐹⊆𝐻𝑖. Since its general introduction by Joos and Kim (Bull. Lond. Math. Soc. 52 (2020)498–504), a growing body of work has shown that inmany cases this lower bound is tight. In this paper, wegive a unified approach to this problem by providinga widely applicable sufficient condition for this lowerbound to be asymptotically tight. This is general enoughto recover many previous results in the area and obtainnovel transversal variants of several classical Dirac-typeresults for (powers of) Hamilton cycles. For example, wederive that any collection of 𝑟𝑛 graphs on an 𝑛-vertex set, each with minimum degree at least (𝑟∕(𝑟 + 1) +𝑜(1))𝑛, contains a transversal copy of the 𝑟th power of a Hamilton cycle. This can be viewed as a rainbow versionof the Pósa–Seymour conjecture.